Một số nguyên dương được gọi là "gần nguyên tố" nếu nó có đúng 3 ước số dương hoàn toàn phân biệt (tính cả 1 và chính số đó).

Ví dụ 25 là gần nguyên tố vì nó có đúng 3 ước số dương là 1, 5 và 25;

Yêu cầu: Cho một số nguyên dương n. Hãy kiểm tra xem số n có phải là số "gần nguyên tố" hay không?

Dữ liệu:

+Dòng thứ nhất ghi một số nguyên dương m;

+m dòng tiếp theo, mỗi dòng chứa một số nguyên dương n.

Kết quả: Ghi ra M dòng:

Dòng thứ i, ghi 1 nếu số n tương ứng là số "gần nguyên tố", ngược lại ghi ra 0.

Ví dụ:

Input

3
25
10
121

Output

1
0
1

Ràng buộc

Có 30% số test ứng với 30% số điểm của bài có m ≤ 10⁵, n ≤ 10³;

Có 30% số test tiếp theo ứng với 30% số điểm của bài có m ≤ 10⁵, n ≤ 10⁶;

Có 40% số test còn lại tương với 40% số điểm của bài có m ≤ 10⁵, n ≤ 10¹².

Nguồn