题目描述

小Y是一位热爱数学的收藏家，他的藏品是一串编号为 $a_1, a_2, \dots, a_n$ 的数字水晶，每一颗水晶都刻有一个正整数。

为了研究水晶的数字规律，小Y定义了一个「区间最大公约值」的概念：对于一段连续的水晶区间 $[l, r]$（要求 $1 \le l < r \le n$），这个值是区间内任意挑选两颗不同水晶，它们刻有的数字的最大公约数中的最大值。

形式化地说，区间 $[l, r]$ 的最大公约值为：

$$\text{maxgcd}(l, r) = \max_{l \le i < j \le r} \gcd(a_i, a_j)$$

现在小Y准备了 $q$ 个研究问题，每个问题都会指定一段水晶区间 $[l_i, r_i]$，请你帮他快速算出每段区间的「区间最大公约值」吧！

---

输入格式

1. 第一行输入一个正整数 $n$，代表数字水晶序列的长度。
2. 第二行输入 $n$ 个正整数 $a_1, a_2, \dots, a_n$，依次代表每颗水晶上刻的数字。
3. 第三行输入一个正整数 $q$，代表小Y提出的问题数量。
4. 接下来 $q$ 行，每行输入两个正整数 $l_i, r_i$，代表第 $i$ 个问题询问的水晶区间。

---

输出格式

对于每个问题，输出一行一个正整数，代表对应区间的「区间最大公约值」。

6
10 20 30 40 50 60
3
1 6
2 5
4 5

30
20
10

样例 1 解释

• 第一个问题询问区间 $[1, 6]$：挑选第3颗（30）和第6颗（60）水晶，$\gcd(30, 60) = 30$，为所有组合中的最大值。
• 第二个问题询问区间 $[2, 5]$：挑选第2颗（20）和第4颗（40）水晶，$\gcd(20, 40) = 20$，为所有组合中的最大值。
• 第三个问题询问区间 $[4, 5]$：挑选第4颗（40）和第5颗（50）水晶，$\gcd(40, 50) = 10$，为所有组合中的最大值。

10
13 2 35 4 13 2 5 1 7 4
5
1 4
4 10
3 8
3 9
1 10

2
4
5
7
13

数据范围

对于所有测试数据，满足：$2 \le n \le 10^5$，$1 \le a_i \le 10^5$，$1 \le q \le 10^5$，$1 \le l_i < r_i \le n$。