ZaloPay là ứng dụng thanh toán di động với nhiều tính năng độc đáo. Được xây dựng chuyên biệt để thỏa mãn mọi nhu cầu thanh toán trong cuộc sống và nhu cầu kinh doanh... Ngoài việc sử dụng ứng dụng ZaloPay trên điện thoại hay sử dụng ZaloPay trực tiếp trên ứng dụng Zalo, bây giờ người dùng có thể truy cập website ZaloPay tại đây để biết thêm các thông tin cũng như sử dụng cách dịch vụ ngay trên website như thanh toán hoá đơn, nạp tiền điện thoại, mua vé xem phim, ...

ZaloPay không chỉ cung cấp các giải pháp thanh toán thông minh mà còn đặc biệt chú trọng đến vấn đề bảo mật thông tin. Một trong những phương pháp bảo mật phổ biến nhất là mã hóa dữ liệu. Mã hóa dữ liệu biến đổi thông tin thành dạng không thể đọc được nếu không có khóa giải mã, giúp bảo vệ thông tin khỏi các cuộc tấn công và truy cập trái phép.

Thông tin người dùng gửi lên được thể hiện bởi một dãy gồm ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~, sau đó máy chủ sẽ tiến hành mã hoá thông tin và tạo ra một số nguyên ~A~ bằng cách tính tích các số trong dãy trên. Để giải mã thông tin được mã hoá trên, bạn cần phải có khoá bí mật, được đại diện bởi một cặp số nguyên dương ~(X, P)~. Một khoá được gọi là hợp lệ nếu ~A~ chia hết cho ~X^P~.

Để có thể truy cập vào tài nguyên, người dùng cần gửi kèm khoá bí mật để máy chủ xác thực. Có ~T~ truy vấn được gửi lên máy chủ, hãy cho biết khoá gửi kèm có hợp lệ hay không?

Input

• Dòng đầu chứa số nguyên dương ~N~ ~(N \le 10^6)~
• Dòng thứ hai chứa ~N~ số nguyên biểu diễn cho dãy số ~(1 \le a_i \le 10^6)~
• Dòng thứ ba chứa số nguyên dương ~T~ - là số lượng truy vấn ~(T \le 5 \times 10^5)~
• ~T~ dòng tiếp theo, mỗi dòng chứa cặp số nguyên ~X~ ~P~ ~(1 \le X, P \le 5 \times 10^5)~

Output

Gồm ~T~ ký tự viết liên tiếp nhau, ký tự thứ ~i~ là ~1~ nếu trong truy vấn thứ ~i~, ~A~ chia hết cho ~X^P~, ngược lại là ~0~

Subtasks

• Subtask 1 (20%): ~A \le 10^9~ và ~X, P \le 10^5~
• Subtask 2 (20%): mọi truy vấn đều có ~P = 1~
• Subtask 3 (20%): ~N, A, X, P \le 10^5~
• Subtask 4 (40%): không có ràng buộc gì thêm

Sample Input

5
1 2 3 4 5
4
5 1
2 3
3 4
15 2

Sample Output

1100

Notes

Trong ví dụ trên, ~A = 1 * 2 * 3 * 4 * 5 = 120~, có tất cả ~4~ truy vấn:

• Truy vấn 1, ~X = 5, P = 1~ và ~A=120~ chia hết cho ~5^1=5~
• Truy vấn 2, ~X = 2, P = 3~ và ~A=120~ chia hết cho ~2^3=8~
• Truy vấn 3, ~X = 3, P = 4~ và ~A=120~ không chia hết cho ~3^4=81~
• Truy vấn 4, ~X = 15, P = 2~ và ~A=120~ không chia hết cho ~15^2=225~