Bumblebee's Malfunction

Time limit2sMemory limit1024 MB

Summary

For each query segment of an array, output the gcd of the mex values over all nonempty subsets of that segment.

Level: Easy3 of 10
Topics: Prefix sum, Implementation
Solved: No attempts yet

Problem

Bumblebee malfunctioned after a fight with the Decepticons. Now he is trying to solve a strange problem. Here is its statement.

Two functions are defined on sets of positive natural numbers. The first is $mex(a_1, a_2, \dots, a_n)$ , the smallest positive natural number that does not appear among $a_1, a_2, \dots, a_n$ . The second is $gcd(a_1, a_2, \dots, a_n)$ , the greatest common divisor of $a_1, a_2, \dots, a_n$ . Bumblebee generated an array of natural numbers and wants to perform the following operation: for given $l$ and $r$ , enumerate all subsets of the segment of the array from $a_l$ to $a_r$ inclusive, compute the $mex$ of each non-empty subset, and then compute the $gcd$ of all the resulting $mex$ values. (It is easy to see that there are $2^{r - l + 1} - 1$ of them.)

Bumblebee's computing power is not enough to solve this quickly. Help him.

Input

The first line contains the number $n$ ( $1 \le n \le 10^5$ ), the length of the array.

The second line contains $n$ integers $a_i$ separated by spaces ( $1 \le a_i \le 10^9$ ), the elements of the array.

The third line contains the number $q$ ( $1 \le q \le 10^4$ ), the number of queries.

Each of the next $q$ lines contains two integers $l$ and $r$ ( $1 \le l \le r \le n$ ), the segment for which the function value must be computed.

Output

Print $q$ lines. On the $i$ -th line, print the answer to the $i$ -th query.

Examples1

Example 1
Input
```
4
1 2 3 4
2
1 1
1 4
```
Expected output
```
2
1
```