Ta gọi số ngược của một số là số tạo ra bằng cách viết các chữ số của số đã cho theo chiều từ phải qua trái (Ví dụ: số 123 có số ngược là 321).

Một số nguyên X được gọi là số đối lập nếu X cùng với số ngược của nó là những số nguyên tố cùng nhau (tức ước số chung lớn nhất của X và số ngược bằng 1). Ví dụ: số 124 là một số đối lập vì ước số chung lớn nhất của 124 và 421 bằng 1.

Yêu cầu: Lập trình để xác định một số nguyên dương đã cho có phải số đối lập hay không?

Dữ liệu vào:

Tệp văn bản CAU1.INP gồm:

- Dòng 1: Số nguyên dương N (N ≤ 10³).

- N dòng tiếp theo: mỗi dòng chứa một số nguyên dương a_i (a_i ≤ 2×10⁹).

Kết quả:

Ghi ra tệp văn bản CAU1.OUT gồm N dòng, dòng thứ i ghi số 1 nếu số a_i là số đối lập, ngược lại ghi 0.

Ví dụ:

CAU1.INP
3
124
201
2021

CAU1.OUT
1
0
1

Ràng buộc:

- 50% số test: N ≤ 10², a_i ≤ 2×10⁶.
- 20% số test: N ≤ 10³, a_i ≤ 2×10⁶.
- 30% số test: N ≤ 10³, a_i ≤ 2×10⁹.