------Read problems statements in Hindi,
Mandarin chinese
, Russian and Vietnamese as well. ------

Sheokand is good at mathematics. One day, to test his math skills, Kaali gave him an integer $N$. To impress Kaali, Sheokand has to convert $N$ into an integer $M$ that can be represented in the form $2^{x} + 2^{y}$ (where $x$ and $y$ are non-negative integers such that $x \neq y$). In order to do that, he can perform two types of operations:
add $1$ to $N$
subtract $1$ from $N$

However, Sheokand is preparing for his exams. Can you help him find the minimum number of operations required to convert $N$ into a valid integer $M$?

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each testcase contains a single integer $N$.

------ Output ------
For each test case, print a single line containing one integer — the minimum required number of operations.

------ Constraints ------
$1 ≤ T ≤ 100,000$
$1 ≤ N ≤ 10^{9}$

------ Subtasks ------
Subtask #1 (30 points): $1 ≤ T ≤ 1,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------
3
10
22
4
----- Sample Output 1 ------
0
2
1
----- explanation 1 ------
Example case 1: $N=10$ is already in the form $2^{x} + 2^{y}$, with $x=3$ and $y=1$.

Example case 2: $N=22$ can be converted into $M=20=2^{2}+2^{4}$ or $M=24=2^{3}+2^{4}$ in two operations.

Example case 3: $N=4$ can be converted into $M=3=2^{0}+2^{1}$ or $M=5=2^{0}+2^{2}$ in one operation.

见题面

见题面