You are given a number $$N$$. In one operation, you can either increase the value of $$N$$ by 1 or decrease the value of $$N$$ by 1.

Determine the minimum number of operations required (possibly zero) to convert number $$N$$ to a number $$P$$ such that binary representation of $$P$$ is a palindrome.

Note: A binary representation is said to be a palindrome if it reads the same from left-right and right-left.

Input format

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

Output format

For each test case in a new line, print the minimum number of operations required. 

Constraints

\(1 \le T \le 10^5 \\ 0 \le N \le 2 \times 10^9\)