Cho ~ n = 10^5 ~ số nguyên dương ~ a_1 , a_2 , ... , a_n ~ . Với mỗi ~ i = 1 , 2 , ... , n ~.

Hãy kiểm tra xem ~ a_i ~ có phải số nguyên tố không?

Input

• Gồm ~ n ~ dòng , dòng thứ ~ i ~ là số nguyên dương ~ a_i ~(~ 1 \le a_i \le 2^{53} ~)

Output

• Gồm ~ n ~ dòng , dòng thứ ~ i ~ ghi ra số 1 nếu ~ a_i ~ là số nguyên tố , ngược lại ghi ra 0 .

Sample

Input #1

3
5
6

Output #1

1
1
0

Hint

• Số 3 là số nguyên tố nên ghi ra;
• Số 5 là số nguyên tố nên ghi ra;
• Số 6 không là số nguyên tố nên ghi ra.

Problem source: Chuyên Sơn La Online Judge