题目描述

浮生如梦，百年如露。

虾仁不会数学，也不想做这个数学题，嘤嘤嘤！

给定一个长度为 $n$ 的数列，数列的每一项为 $a_i$。你需要回答以下 $q$ 个问题，每个问题会询问一对 $l,r$，你可以从 $a_l,a_{l+1},\dots,a_r$ 中选择一些数，不能不选。

假设你选了 $m$ 个数 $a_{p_1},a_{p_2},\dots,a_{p_m}$，你需要保证 $\gcd(a_{p_1},a_{p_2},\dots,a_{p_m})^{\dagger}$ 是这个区间里对于任意一种选数情况的最大值。请回答这个最大的 $\gcd(a_{p_1},a_{p_2},\dots,a_{p_m})$ 是多少。

$^{\dagger}$ 表示 $a_{p_1},a_{p_2},\dots,a_{p_m}$ 之间的最大公约数。

输入格式

第一行一个整数 $n\ \left(1 \le n \le 2 \times 10^5\right)$ 表示数列长度。

第二行 $n$ 个整数 $a_i\ \left(1 \le a_i \le 10^6\right)$ 以空格隔开，表示数列。

第三行一个整数 $q\ \left(1 \le q \le 2 \times 10^5\right)$ ，表示询问个数。

下面 $q$ 行每行两个整数 $l,r\ \left(1 \le l \le r \le n\right)$ ，表示区间。

输出格式

输出 $q$ 行，每行一个整数表示答案。

样例输入

2
1 2 
2
1 1
2 2

样例输出

1
2

样例解释

无