# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# A Journey Towards One

By moshiur_cse15 · Limits 1s, 256 MB

Given $N$. You can perform 3 types of operations:

1. Increase $N$ by 1.
2. Decrease $N$ by 1.
3. Divide $N$ by 2, available only when $N$ is even.

You have to find the minimum number of operations needed to reach 1.

## Input

The first line of the input will contain an integer $T$ ($1 \le T \le 10^6$), the number of test cases. Each of the next T lines will contain an integer $N$ ($1 \le N \le 10^6$), as described in the problem statement.

## Output

For each test case, you have to find the minimum number of operations needed to reach 1.

## Sample

InputOutput
5
2
3
4
5
23

1
2
2
3
6


### Statistics

85% Solution Ratio

qwerty321Earliest, Jan '20

nabil_mashriefFastest, 0.1s

MahmudXLightest, 3.0 MB

GameLordShortest, 259B