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\le T\le {10}^6$

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