밤블비의 고장

밤블비는 디셉티콘과 싸운 뒤 고장이 났다. 지금 그는 이상한 문제를 풀려고 한다. 문제 조건은 다음과 같다.

양의 자연수 집합에 대해 두 함수를 정의한다. 첫 번째 함수는 $mex(a_1, a_2, \dots, a_n)$으로, $a_1, a_2, \dots, a_n$ 중에 없는 가장 작은 양의 자연수이다. 두 번째 함수는 $gcd(a_1, a_2, \dots, a_n)$으로, $a_1, a_2, \dots, a_n$의 최대공약수이다. 밤블비는 자연수 배열을 만들었고, 다음 연산을 하고 싶어 한다. 주어진 $l$, $r$에 대해 배열의 $a_l$부터 $a_r$까지 구간의 모든 부분집합을 나열하고, 공집합이 아닌 각 부분집합의 $mex$를 구한 뒤, 얻은 모든 $mex$의 $gcd$를 계산한다. (이때 $mex$는 $2^{r - l + 1} - 1$개가 나온다는 것을 쉽게 알 수 있다.)

밤블비의 계산 능력으로는 이 문제를 빠르게 풀 수 없다. 그를 도와라.

첫 줄에 배열의 길이 $n$ ($1 \le n \le 10^5$)이 주어진다.

둘째 줄에는 공백으로 구분된 $n$개의 정수 $a_i$ ($1 \le a_i \le 10^9$)가 주어진다.

셋째 줄에는 질의의 개수 $q$ ($1 \le q \le 10^4$)가 주어진다.

이후 $q$개의 줄에 각각 두 정수 $l$, $r$ ($1 \le l \le r \le n$)이 주어진다. 이는 함수의 값을 구해야 하는 구간이다.

$q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질의의 답을 출력한다.