Recently a company came into existence and had a impressive growth over past 2 years. The assets of the company is given by the P-value. The value is calculated by GCD of all contributions presented in the form of an array.

Let us call the prefix of size K of array A as another array which contains only first K elements of array A. You are given contributions in form of array A. Founder of company wanted to know the minimum size of prefix that could be removed such that P-value remaining array is maximised.

Also Q queries are given and in each query a range is given by L and R and we have to find the maximum GCD that can be obtained by removing a prefix K of any size in the given range.

INPUT:
First line contains an integer N denoting the size of array A.
Next line contains N space separated integers denoting the array A.
Next line contains an integer Q.
Then follow Q lines each represented using two integers L and R.

OUTPUT:
Firstly, print a single integer, the size of the prefix that should be removed so that the P−Value of the remaining array is maximised.
If there are several possible answers, print the length of minimum size prefix.
After it Q lines follow each representing the answer related to each query.

CONSTRAINTS:
2 ≤ N ≤ $10^{5}$
1 ≤ A[i] ≤ $10^{6}$
1 ≤ Q ≤ $10^{5}$
1 ≤ L ≤ R ≤ N