C. Flip the Bits
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a positive integer n. Your task is to build a number m by flipping the minimum number of bits in the binary representation of n such that m is less than n (m < n) and it is as maximal as possible. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 105) specifying the number of test cases.

Each test case consists of a single line containing one integer n (1 ≤ n ≤ 109), as described in the statement above.

Output

For each test case, print a single line containing the minimum number of bits you need to flip in the binary representation of n to build the number m.

Example
Input
2
5
10
Output
1
2