GCD requests

Input

The first line contains a single integer $n$ (2 \le n \le 2 \cdot 10^5 ) — the size of the array.

The second line contains $n$ integers a_1, a_2, \ldots, a_n (1 \le a_i \le 10^6) — the elements of the array.

The third line contains a single integer $m$ (1 \le m \le 2 \cdot 10^5 ) — the number of queries.

Each of the next $m$ lines contains two integers l_i, r_i (1 \le l_i < r_i \le n) — the boundaries of the query.

Output

For each query, output a single integer — the answer to that query.

Examples

Note

\gcd(a, b) denotes the greatest common divisor of numbers $a$ and $b$.

Consider the second example:

• In the first four queries, the segment consists of only two numbers, so the answer is their greatest common divisor.

• Query $(1,5)$: the greatest common divisor is for numbers a_1 and a_4, \gcd(a_1, a_4)=\gcd(10, 50)=10.

• Query $(3,5)$: calculate \max(\gcd(a_3, a_4), \gcd(a_3, a_5), \gcd(a_4, a_5))=\max(2, 3, 1) = 3.

• Query $(1,3)$: calculate \max(\gcd(a_1, a_2), \gcd(a_1, a_3), \gcd(a_2, a_3))=\max(1, 2, 3) = 3.

Scoring

1. ($12$ points): m, n, a_i \leq 200;

2. ($7$ points): m, n \leq 200;

3. ($17$ points): a_i \leq 50;

4. ($7$ points): all a_i are powers of two;

5. ($27$ points): m, n \leq 15000;

6. ($13$ points): m, n \leq 35000;

7. ($17$ points): no additional constraints.