整数列と、その列内のいくつかの区間が与えられます。区間は左端と右端の位置で指定されます。$k$ 個の整数からなる区間には、異なる位置の整数の組が $k(k-1)/2$ 個あり、それぞれに最大公約数があります。与えられた各区間について、それらの最大公約数の最大値を求めてください。
例えば、列が $(a_1,\ldots,a_6)=(10,20,30,40,50,60)$ で、列全体が区間として指定された場合、異なる位置 $x,y$ にある二つの整数の次の 15 組と、その最大公約数を考えます。
| $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$ です。
入力
入力は、次の形式の単一のテストケースからなります。
$$\begin{array}{l}n\\a_1\ \cdots\ a_n\\q\\l_1\ r_1\\\vdots\\l_q\ r_q\end{array}$$
最初の行には、与えられる列の整数の個数を表す整数 $n$ ($2\le n\le 10^5$) が与えられます。2 行目には、列を指定する $n$ 個の正の整数 $a_1,\ldots,a_n$ が与えられます。いずれも $10^5$ 以下です。
3 行目には、考える区間の個数を表す正の整数 $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