Description

AzureHair 的同学把 AzureHair 和 $n$ 只猫猫关在一个房间里，并且要求 AzureHair 每过一天就交出 $\frac{n}{2}$ 只猫猫，但是如果 $n$ 是奇数时，AzureHair 就会纠结于要交出 $\frac{n+1}{2}$ 只猫猫还是交出 $\frac{n-1}{2}$ 只猫猫。AzureHair 不想让自己纠结，所以请你计算出直到所有猫猫都被拿出房间时，AzureHair 的最小纠结次数是多少。

Input Format

本题有多组测试数据。

第一行一个整数 $T$。

接下来 $T$ 行，每行一个整数 $n$。

Output Format

$T$ 行，每行一个整数表示最小纠结次数。

2
13
7

3
2

Hint

【样例解释】

对于 $13$ 只猫猫，只纠结 $3$ 次的过程如下：

选择交出 $7$ 只猫猫，剩余 $6$ 只；

不纠结，交出 $3$ 只猫猫，剩余 $3$ 只；

选择交出 $2$ 只猫猫，剩余 $1$ 只；

选择交出 $1$ 只猫猫，所有猫猫均被取走。

容易证明不存在少于 $3$ 次纠结的方案。

【数据范围】

对于 $10\%$ 的数据，保证 $1\le n \le 10$。

对于 $30\%$ 的数据，保证 $1\le n \le 10^{5}$。

对于 $100\%$ 的数据，保证 $1\le n \le 2^{60}$，$1 \le T \le 5\times 10^5$。