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}\)