Số đối lập

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ụ: \(123\) có số ngược là \(321\)).

Một số nguyên dương \(X\) được gọi là số đối lập nếu \(X\) và số ngược của nó là hai số nguyên tố cùng nhau.

Với mỗi số \(a_i\), hãy xác định xem \(a_i\) có phải là số đối lập hay không.

Input

Dữ liệu vào từ tệp CAU1.INP:

• Dòng \(1\): Số nguyên dương \(N\) \((N \le 10^3)\).
• \(N\) dòng tiếp theo: Mỗi dòng chứa một số nguyên dương \(a_i\) \((a_i \le 10^9)\).

Output

Ghi ra tệp CAU1.OUT gồm \(N\) dòng, dòng thứ \(i\):

• Ghi \(1\) nếu \(a_i\) là số đối lập, ngược lại ghi \(0\).

Input

%
3
123
201
2021

Output

%
0
0
1

Scoring

• (50%) \(N \le 10^2\), \(a_i \le 10^6\).
• (20%) \(N \le 10^3\), \(a_i \le 10^6\).
• (30%) \(N \le 10^3\), \(a_i \le 10^9\).