Cho ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Với mỗi số ~a_i~, 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~. (~n \le 10^5~, ~1 \le a_i \le 2^{53}~)

OUTPUT

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

SAMPLE INPUT

3
5
6

SAMPLE OUTPUT

1
1
0