Problem Statement
 Given a number , find whether it is a power of 2 or not
NOTE There is a limit in Source code.

Input
The first Line contains T , the no of test cases followed by T lines.
Each line has a integer X

Output
Output has T lines , with each line indicating whethet the number is a power of 2 or not(print 1 if it a power of two else print 0)

Example

Input

4
4
0
6
8

Output

1
0
0
1

见题面

见题面