You are given a number $N$. Your task is to find if there exist two distinct natural numbers such that their bitwise $XOR$ is $N$ and bitwise $AND$ is $0$. If such numbers exist, then print $1$. Otherwise, print $0$.

 Input format

• The first line contains $T$ denoting the number of test cases.
• The first line of each test case contains an integer $N$.

Output format

For each test case, print the answer.

Constraints

$1 \leq T \leq 10^6$

$0 \leq N \leq 10^{18}$