After a frustrating internship season, adkroxx was still applying everywhere. Adkroxx has to solve the following problem to get an internship.

The recruiter gives adkroxx a number N and ask him to find two numbers A and B (0 < A,B < N) such that (A*B) modulo N is equal to zero.He has to determine whether such A,B exists or not. Adkroxx will only get an internship if such A,B exists so please help him out.

Input format:

First line of the input contains an integer T, denoting the number of testcases.

The first line of every test case contains a number N.

Output format:

Output “1”(without quotes) in a new line for every test case if it is possible to find such A,B and “0“(without quotes) otherwise.

Constraints:

1 ≤ T ≤ 10000

1 < N ≤ 10^{10}

Sample Input:

2

3

12

Sample Output:

0

1

Explanation:

For N=3, possible values for (A*B)%N are (2*2)%3=1 , (1*1)%3=1 , (1*2)%3=2.

For N=12 (6*6)%12=0.

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED

2 months ago

java

0.00 sec

0 KB

7 months ago

java

0.10 sec

416 KB

7 months ago

java

0.13 sec

416 KB

7 months ago

cpp

1.10 sec

2376 KB

7 months ago

cpp

2.00 sec

308 KB

7 months ago

cpp

0.07 sec

64 KB

7 months ago

cpp

0.07 sec

64 KB

7 months ago

cpp

1.24 sec

448 KB

7 months ago

cpp

0.07 sec

64 KB

7 months ago

cpp14

1.51 sec

97960 KB

7 months ago

cpp14

0.08 sec

976868 KB