실시간으로 주어지는 \(M\)개의 수들에 대해, 각 수가 2의 거듭제곱인지 판별하는 프로그램을 작성하시오.

입력

첫째 줄에 판별해야 하는 수의 개수 \(M\)이 주어진다.

둘째 줄부터 \(M\)개의 줄에 걸쳐 판별해야 하는 양의 정수 \(X\)가 한 줄에 하나씩 주어진다.

출력

입력으로 주어지는 \(X\)에 대해, 2의 거듭제곱이 맞다면 1을, 아니라면 0을 한 줄에 하나씩 순서대로 출력한다.

제한사항

• \(1 \le M \le 2000000\)
• \(1 \le X \le 5 \times 10^{18}\)

예제 입력 1

7
1
3
4
6
1024
500000000000000000
4611686018427387904

예제 출력 1

1
0
1
0
1
0
1