给定一个整数序列和若干个序列区间。区间由其最左侧和最右侧的位置指定。一个包含 $k$ 个整数的区间共有 $k(k-1)/2$ 对位于不同位置的整数，我们需要考虑这些整数对的最大公约数。对于每个给定的区间，求出这些最大公约数中的最大值。
例如，当序列为 $(a_1, \dots, a_6) = (10, 20, 30, 40, 50, 60)$，且整个序列被指定为一个区间时，需要考虑以下 15 对位于不同位置 $x$ 和 $y$ 的整数及其最大公约数。
| $x$ | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 4 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $y$ | 2 | 3 | 4 | 5 | 6 | 3 | 4 | 5 | 6 | 4 | 5 | 6 | 5 | 6 | 6 |
| $a_x$ | 10 | 10 | 10 | 10 | 10 | 20 | 20 | 20 | 20 | 30 | 30 | 30 | 40 | 40 | 50 |
| $a_y$ | 20 | 30 | 40 | 50 | 60 | 30 | 40 | 50 | 60 | 40 | 50 | 60 | 50 | 60 | 60 |
| $\gcd(a_x, a_y)$ | 10 | 10 | 10 | 10 | 10 | 10 | 20 | 10 | 20 | 10 | 10 | 30 | 10 | 20 | 10 |
在这种情况下，这 15 对最大公约数中的最大值为 $\gcd(30, 60) = 30$。
输入格式
输入包含单个测试用例，格式如下：
$n$ $a_1 \dots a_n$ $q$ $l_1 \ r_1$ $\vdots$ $l_q \ r_q$
第一行包含一个整数 $n$，表示给定序列中整数的个数，满足 $2 \le n \le 10^5$。第二行包含 $n$ 个正整数 $a_1$ 到 $a_n$，指定该序列。其中每个数均不超过 $10^5$。
第三行包含一个正整数 $q$，表示需要考虑的序列区间数量，不超过 $10^5$。随后有 $q$ 行，每行指定一个需要考虑的序列区间。第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i < r_i \le n$)，指定序列中从 $a_{l_i}$ 到 $a_{r_i}$ 的区间。
输出格式
输出 $q$ 行，第 $i$ 行应包含由 $l_i$ 和 $r_i$ 指定的区间内所有整数对的最大公约数中的最大值。
样例
输入 1
6 10 20 30 40 50 60 3 1 6 2 5 4 5
输出 1
30 20 10
输入 2
10 13 2 35 4 13 2 5 1 7 4 5 1 4 4 10 3 8 3 9 1 10
输出 2
2 4 5 7 13