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 NN. You can perform 3 types of operations:

  1. Increase NN by 1.
  2. Decrease NN by 1.
  3. Divide NN by 2, available only when NN 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 TT (1T1061 \le T \le 10^6), the number of test cases. Each of the next T lines will contain an integer NN (1N1061 \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

Discussion

Statistics


85% Solution Ratio

qwerty321Earliest, Jan '20

nabil_mashriefFastest, 0.1s

MahmudXLightest, 3.0 MB

GameLordShortest, 259B

Submit

Login to submit

Editorial

If you analyze, you’ll find it is better to divide NNN by 2 when available. So, dp[n] = 1 + dp[n / 2...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.