Abstract art, like abstract problems, is very enjoyable.

You see an abstract problem on Codeforces.

Given an integer ~x~ you want to change ~0~ into that number using a minimal number of the following operations:

• Add ~1~
• Subtract ~1~
• Multiply by ~2~

You think it is too easy, so you increase ~x~ to ~X~ ~(1 \le X < 2^{63})~, and decide that you should answer ~T~ ~(T \le 300\,000)~ of these queries per test case.

Input Specification

The first line of input will contain ~T~.

The next ~T~ lines of input will each contain ~X~.

Output Specification

For each ~X~, output on separate lines the minimal number of operations necessary to change ~0~ into ~X~.

Sample Input

2
32
15

Sample Output

6
6