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 300000)$ 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