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.

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\)).

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

```
3
1
2
3
```

```
2
1
3
```