GCD requests

You are given an array of non-negative integers of length $n$ and $m$ queries. Each query consists of two numbers $l$ and $r$. For each query, determine the maximum of the greatest common divisors (GCD) of all pairs in the subarray from $l$ to $r$. Specifically, find:

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,\dots ,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\le 200$;

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

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

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

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

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

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