Description

For a sequence of positive integers $\boldsymbol{X} = (X_1, X_2, \ldots, X_M)$ where $M \geq 2$, let $f(\boldsymbol{X})$ be the answer to the following problem:

• Among the $M$ positive integers $X_1, X_2, \ldots, X_M$, paint at least one and at most $M - 1$ of them red, and paint the rest blue. Let $R$ be the greatest common divisor (GCD) of the integers painted red, and $B$ be the GCD of the integers painted blue. Find the maximum possible value of $R + B$.

You are given a sequence of $N$ positive integers $\boldsymbol{A} = (A_1, A_2, \ldots, A_N)$. You will also be given $Q$ queries. For each query, you will be given two integers $l_i$ and $r_i$ such that $1 \leq l_i < r_i \leq N$. For each query, let $\boldsymbol{X} = (A_{l_i}, A_{l_i + 1}, \ldots, A_{r_i})$, and find $f(\boldsymbol{X})$.

Input Format

The input is given in the following format:

$$\begin{aligned} &N \\ &A_1 \ A_2 \ \ldots \ A_N \\ &Q \\ &l_1 \ r_1 \\ &l_2 \ r_2 \\ &\vdots \\ &l_Q \ r_Q \end{aligned}$$

• $2 \leq N \leq 200,000$
• $1 \leq A_i \leq 10^{18}$ for all $1 \leq i \leq N$
• $1 \leq Q \leq 200,000$
• $1 \leq l_i < r_i \leq N$ for all $1 \leq i \leq Q$

Output Format

Print $Q$ lines. On the $i$-th line ($1 \leq i \leq Q$), output the answer to the $i$-th query.

6
3 6 2 5 4 4
3
1 3
4 6
1 6

7
9
7