Cho dãy số \(A\) gồm \(N\) phần tử \(A_1, A_2, \dots, A_N\). Có \(M\) câu hỏi, mỗi câu hỏi yêu cầu tìm ước chung lớn nhất (GCD) của các phần tử trong đoạn từ \(L\) đến \(R\).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\).
• Dòng thứ ba chứa số nguyên dương \(M\) là số lượng câu hỏi.
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L_i, R_i\) đại diện cho một câu hỏi.

Output

• Gồm \(M\) dòng, mỗi dòng là kết quả GCD của đoạn tương ứng.

Example

5
34 23 12 34 2 
3
1 3
2 4
5 5

1
1
2

Constraints

• \(1 \le N, M \le 5 \cdot 10^5\)
• \(1 \le A_i \le 10^9\)
• \(1 \le L_i \le R_i \le N\)