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ó ước số chung lớn nhất bằng \(1\)). Ví dụ: số \(123\) là một số đối lập vì ước số chung lớn nhất của \(123\) và \(321\) bằng \(1\). Nhiệm vụ của bạn là 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?

Input

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

Output

• Ghi ra \(N\) dòng, dòng thứ \(i\) ghi số \(1\) nếu số \(a_i\) tương ứng là số đối lập, ngược lại ghi số \(0\).

Example

3
123
201
2021

1
0
1

Constraints

• Có \(50\%\) số test cho \(N \le 10^2\) và \(a_i \le 2 \cdot 10^6\).
• Có \(20\%\) số test cho \(N \le 10^3\) và \(a_i \le 2 \cdot 10^6\).
• Có \(30\%\) số test cho \(N \le 10^3\) và \(a_i \le 2 \cdot 10^9\).