A Journey Towards One

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

Input	Output
5 2 3 4 5 23	1 2 2 3 6