J. Crystal Combination
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Elaina, a magic teacher, has prepared an exam with $$$t$$$ questions. In each question, given a target magic power $$$x$$$, a student must combine exactly two magic crystals with powers $$$2^{a}$$$ and $$$2^{b}$$$ for some non-negative integers $$$a$$$ and $$$b$$$ (possibly $$$a = b$$$), and report the minimum possible difference between the combined power and $$$x$$$, that is, $$$\left|2^{a} + 2^{b} - x\right|$$$. Please help the students finish the exam.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$. The description of the test cases follows.

The only line of each test case contains one integer $$$x$$$, representing the target magic power.

  • $$$1 \leq t \leq 10^4$$$
  • $$$1 \leq x \leq 10^{18}$$$
Output

For each test case, output one integer: the minimum possible difference between the combined power and $$$x$$$, that is, $$$\left|2^{a} + 2^{b} - x\right|$$$.

Example
Input
3
7
10
1
Output
1
0
1