Trong lớp học toán của thầy Lữ, có ~n~ học sinh.

Ngày hôm nay, thầy Lữ đã yêu cầu ~n~ bạn học sinh của mình mỗi người chọn một số nguyên dương lớn hơn ~0~. Được biết nếu một bạn học sinh chọn số nguyên dương ~k~ thì bạn đó sẽ yêu thích các số nguyên dương là ước của ~k~.

Ví dụ: Nam chọn số 10, thì bạn đó sẽ yêu thích các số nguyên: ~1, 2, 5, 10~.

Khi nhìn vào dãy các con số mà học sinh của mình đã chọn. Thầy Lữ đã đặt ra một câu hỏi không biết giá trị yêu thích chung lớn nhất của các nhóm bạn học sinh từ vị trí ~l~ đến vị trí ~r~ là bao nhiêu .

Giá trị yêu thích chung lớn nhất của một nhóm là số nguyên dương lớn nhất mà tất cả các bạn trong nhóm đó đều yêu thích nó.

Do là người bận rộn với công việc nên Thầy Lữ đã nhờ bạn trả lời các câu hỏi trên giúp thầy.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~ là số lượng học sinh của lớp học toán.

Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^9)~.

Dòng tiếp theo chứa số nguyên ~m~ ~(1 \le m \le 2 * 10^6)~ là số lượng câu hỏi của thầy Lữ,

~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l, r~ ~(1 \leq l \le r \leq n)~.

Output

Xuất ra ~m~ dòng, với mỗi dòng là câu trả lời tương ứng cho các câu hỏi của thầy Lữ.

Simple Input

5
1 2 3 4 8
3
4 5
2 5
1 2

Simple Output

4
1
1