Một số được định nghĩa là số bán nguyên tố khi và chỉ khi nó chỉ có 3 ước.

Yêu cầu: Với ~q~ truy vấn cho trước hãy kiểm tra xem ~n~ có phải số bán nguyên tố hay không? Nếu có hãy in ra 1 ngược lại in ra 0.

INPUT

• Dòng đầu chứa số ~q~ ~(q <= 10^5)~
• ~q~ dòng tiếp theo, mỗi dòng chứa số ~n~ ~(n <= 10^{12})~

OUTPUT

• Gồm ~q~ dòng, mỗi dòng hãy in ra yêu cầu của bài toán

SUBTASKS

• Subtask 1 (30%): ~q <= 10^5, n <= 10^3~
• Subtask 2 (30%): ~q <= 10^5, n <= 10^6~
• Subtask 3 (40%): ~q <= 10^5, n <= 10^{12}~

SAMPLE

Input

3
1
3
4

Output

0
0
1

Explanation

Các ước của: 
1: 1
3: 1 3
4: 1 2 4