Migrated from Lutece 593 flip

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Give you a non-negative integer $x$ and an operation. The only operation you can do is to reverse one bit in binary form of $x$ once(i.e $1\rightarrow 0$, $0\rightarrow 1$).

your goal is to turn $x$ into $x+1$.

Calculate the minimum times of operations you need to do.

Input

The first line of the input is an integer $T$ indicates the test cases.

Then follow $T$ lines. Each line is a non-negative integer $x$ as described above, note that $0\leq x<10^9$.

Output

Output the minimum times of operations you need to do to reach the goal.

Samples

3
1
2
3

2
1
3

Resources

Sichuan University Programming Contest