Range GCD Query

Given \(n\) positive integers \(a_1, a_2, \dots, a_n\).

There are \(m\) queries. In each query, you are given an interval \([l, r]\). Your task is to compute the greatest common divisor (GCD) of the numbers \(a_l, a_{l+1}, \dots, a_r\).

inputFormat

The first line contains a single integer \(n\) indicating the number of elements.

The second line contains \(n\) space-separated positive integers \(a_1, a_2, \dots, a_n\).

The third line contains a single integer \(m\) indicating the number of queries.

Each of the next \(m\) lines contains two space-separated integers \(l\) and \(r\), which represent a query.

outputFormat

For each query, output a single line containing the GCD of the numbers in the specified interval.

sample

5
2 4 6 8 10
3
1 5
2 4
3 3

2
2
6