# 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