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?
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.
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.
2
5
10
1
2