对于一个正整数序列 $x = (x_1, x_2, \dots, x_k)$（其中 $k \ge 2$），令 $f(x)$ 为以下问题的答案：

在 $k$ 个正整数 $x_1, x_2, \dots, x_k$ 中，将至少一个且至多 $k - 1$ 个数染成洋红色（magenta），其余的数染成青色（cyan）。设 $d_m$ 为染成洋红色的整数的最大公约数（GCD），$d_c$ 为染成青色的整数的最大公约数。求 $d_m + d_c$ 的最大可能值。

给你一个由 $n$ 个正整数组成的序列 $a = (a_1, a_2, \dots, a_n)$。同时还会给出 $q$ 个询问。对于每个询问，你会得到两个整数 $\ell_i$ 和 $r_i$，满足 $1 \le \ell_i < r_i \le n$。对于每个询问，令 $x = (a_{\ell_i}, a_{\ell_i+1}, \dots, a_{r_i})$，求 $f(x)$。

输入格式

第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^{18}$）。

第三行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$）。

接下来的 $q$ 行，每行描述一个询问，包含两个整数 $\ell_i$ 和 $r_i$（$1 \le \ell_i < r_i \le n$）。

输出格式

对于每个询问，输出一个整数：$f(x)$ 的值。

样例

输入样例 1

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

输出样例 1

7
9
7