Cho hàm \(f\) được xác định trên tập hợp các số nguyên dương như sau:

• M(n) = 1 nếu n = 1
• M(n) = 0 nếu có ước số nguyên tố của n xuất hiện trong n hơn một lần
• M(n) = \((-1)^p\)

Ví dụ:

• M(78) = -1 do 78 = 2 x 3 x 13
• M(34) = 1 do 34 = 2 x 17
• M(45) = 0 do 45 = 3 x 3 x 5

Input

• Số lượng bộ test \(t\)
• \(t\) dòng tiếp theo chứa một số nguyên \(n\)

Output

• Xác định M(n).

Example

Sample input

3
78
34
45

Sample output

-1
1
0