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$