Hợp số là số nguyên dương lớn hơn 1 và có nhiều hơn 2 ước.

Yêu cầu: Hãy kiểm tra ~N~ số nguyên ~a_1, a_2,.., a_N~ có phải là hợp số hay không?

Dữ liệu vào:

Đọc dữ liệu từ file HOPSO.INP có cấu trúc như sau:

• Dòng 1 gồm 1 số nguyên dương ~N~ (~N ≤ 10^5~)
• N tiếp theo ghi các số nguyên ~a_1, a_2,.., a_N~ (~0 < a_i ≤ 10^5~)

Dữ liệu ra:

Ghi vào file HOPSO.OUT gồm:

• ~N~ dòng, nếu ~a_i~ là hợp số thì ghi 1, nếu ~a_i~ không phải là hợp số ghi số 0.

Ví dụ:

input

3
1
3 
16

Output

0
0
1