Flip

Frog have a non-negative integer x, and her goal is turning x into x + 1. The only operation she can perform is reversing one bit of x once(i.e \(1 \rightarrow 0\), \(0 \rightarrow 1\)). Please calculate the minimum of operations frog need.

Input

The first line of the input is an integer T, indicating the number of tests.

Each of the following T lines contains a non-negative integer x(\(0 \leq x < 10^9\)).

Output

For each test, output the minimum of operations frog need.

Sample Input

    3
    1
    2
    3

Sample Output

    2
    1
    3