Exponentiating by squaring is a general method for fast computation of large integer powers of a number.The same idea allows fast computation of large exponents.

For example, the evaluation of

     x^13 = ((x^2 · x)^2)^2 · x

This algorithm needs only 5 multiplications instead of 12 (13-1).

Write a program that reads the parameters of the algorithm from the standard input, computes the number of multiplications we need, and writes the result to the standard output.

Input

The input begins with the integer t, the number of test cases. Then t test cases follow. For each test case the first and only line of the input contains exactly one integer n.

0 <= n <= 10^18

Output

For each test case the output contains exactly one integer equal to the number multiplications we have to compute in this given algorithm.

Example

Input:
3
3
5
1

Output:
2
3
4