Range GCD Queries

You are given an array of n positive integers. You need to answer q queries. Each query consists of two indices l and r (0-indexed) which represent the range from l to r (inclusive). For each query, compute the greatest common divisor (GCD) of all the numbers in the specified range.

The GCD of two numbers \(a\) and \(b\) is defined as:

[ gcd(a, b) = \begin{cases} a, & b = 0 \ gcd(b, a \bmod b), & b \neq 0 \end{cases} ]

You may use this property: if at any point the GCD becomes 1, you can stop processing further since \(gcd(1, x) = 1\) for any \(x\).

inputFormat

The input is given via standard input and has the following format:

1. The first line contains a single integer n representing the number of elements in the array.
2. The second line contains n space-separated integers denoting the elements of the array.
3. The third line contains a single integer q representing the number of queries.
4. Then q lines follow, each containing two space-separated integers l and r denoting the start and end indices of a query.

outputFormat

For each query, output the GCD of the subarray from index l to r (inclusive) on a separate line via standard output.

## sample

5
12 15 18 24 30
2
1 3
0 4

3
3

</p>