정수 수열과 이 수열의 여러 구간이 주어집니다. 각 구간은 가장 왼쪽 위치와 가장 오른쪽 위치로 지정됩니다. $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$)이 주어집니다. 두 번째 줄에는 수열을 지정하는 $n$개의 양의 정수 $a_1,\ldots,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