Given a number n, check whether it is a power of two or not.

An integer n is a power of two, if there exists an integer x such that n = 2x.

Example:

2, 4, 8, 16 are powers of 2, while 3, 5, 6, 7 are not.

Testing

Input Format

The first line contains ‘T’ denoting the number of test cases.

For each test case, there exists one line containing the number ‘n’.

Output format

For each test case, the output contains one line with 1 if n is the power of 2 otherwise it contains 0.

Sample Input

5
1
2
3
4
5

Expected Output

1
1
0
1
0

Constraints

1 <= T <= 105
-231 < n < 231