说明

对于一个由正整数构成的序列 $\boldsymbol{X} = (X_1, X_2, \ldots, X_M)$（其中 $M \geq 2$），定义 $f(\boldsymbol{X})$ 为以下问题的答案：

• 在 $M$ 个正整数 $X_1, X_2, \ldots, X_M$ 中，将至少一个、至多 $M - 1$ 个数涂成红色，其余数涂成蓝色。令 $R$ 为所有被涂成红色的数的最大公约数（GCD），$B$ 为所有被涂成蓝色的数的最大公约数。求 $R + B$ 可能的最大值。

给定一个由 $N$ 个正整数构成的序列 $\boldsymbol{A} = (A_1, A_2, \ldots, A_N)$。接下来会给出 $Q$ 个查询。对于每个查询，会给定两个整数 $l_i$ 和 $r_i$，满足 $1 \leq l_i < r_i \leq N$。对于每个查询，令 $\boldsymbol{X} = (A_{l_i}, A_{l_i + 1}, \ldots, A_{r_i})$，求 $f(\boldsymbol{X})$。

输入格式

输入以如下格式给出：

$$\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 i \leq N$，有 $1 \leq A_i \leq 10^{18}$
• $1 \leq Q \leq 200,000$
• 对于所有 $1 \leq i \leq Q$，有 $1 \leq l_i < r_i \leq N$

输出格式

输出 $Q$ 行。在第 $i$ 行（$1 \leq i \leq Q$）输出第 $i$ 个查询的答案。

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

7
9
7

提示

翻译由 DeepSeek V3.2 完成