Sushi Shop Selection

W has finally opened a sushi shop in BG after much planning. However, when L arrives, she decides to pick sushi plates according to her own special rules. The sushi dishes are arranged in a row with positions numbered from 1 to N. Each plate holds a fixed number of sushi pieces which cannot be altered between selections.

At each ordering time, L selects a contiguous segment [l, r] from the row. From that segment she picks one plate, and she picks another plate from outside the segment (if any exists). Even though the chef can quickly replenish the sushi counts, L’s rule is all about the way she eats:

• After picking two plates with sushi counts a and b, she chooses a number D such that every bite eats exactly D sushi pieces.
• She must be able to eat each plate completely with bites of exactly D pieces – that is, D must divide both a and b exactly.
• If more than one D works, her happiness is equal to the value of D (and she wants the biggest possible bite!).

For example, if the two plates have counts 2 and 4, then valid values for D are 1 and 2 (with happiness 2 being maximum), whereas if they are 3 and 5, only D = 1 works.

If L is unable to pick two plates (i.e. if her segment covers the entire set), her happiness is defined as 0.

Your task is: given the numbers on the sushi plates and several queries (each query specifying a segment [l, r]), determine the maximum happiness value L can achieve for each query — that is, the maximum possible D (which is the greatest common divisor of some plate from inside [l, r] and some plate from outside [l, r]).

Note: All formulas are in \( \LaTeX \) format. For example, if two plates have values \( a \) and \( b \), the happiness value is the maximum \( D \) such that \( D\mid a \) and \( D\mid b \), in other words, \( D = \gcd(a,b) \).

inputFormat

The first line contains a single integer N representing the number of sushi plates.

The second line contains N space‐separated integers where the i\(^{th}\) integer represents the number of sushi in the i\(^{th}\) plate.

The third line contains an integer Q , the number of queries.

Each of the next Q lines contains two integers l and r (1 ≤ l ≤ r ≤ N), representing a query.

outputFormat

For each query, output the maximum happiness value (i.e. maximum bite size D) L can achieve. If L cannot select two plates (when the segment covers all plates), output 0.

sample

5
6 10 15 3 4
3
2 4
1 3
1 5

3
3
0