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