#P3005. 小胖寻路

小胖寻路

说明

现在有一颗标准完全二叉树(若父结点编号为 $x$ ,则它的两个子结点的编号分别为 $2x$  、$2x+1$)。现在小胖在 $1$ 号节点,如果她想去 $x$ 号节点,最少需要几步 ?

完全二叉树:若设二叉树的深度为 $k$ ,除第 $k$ 层外,其它各层 ($1$ ~ $k-1$ ) 的结点数都达到最大个数,第 $k$ 层所有的结点都连续集中在最左边。

例如(图为一棵标准的完全二叉树):

二叉树1.png

输入格式

第一行输入一个整数 $T$,表示输入的数据组数。

接下来的 $T$ 行,输入一个整数 $x$ ,表示小胖想去 $x$ 号节点。

$1 \le T \le 10^3$ ,$1 \le x  \le 10^3$

输出格式

对于每组数据,请在独立的行中输出一个整数 $num$ ,表示小胖从 $1$ 号节点走到 $x$ 号节点最少需要几步。

样例

4
1
2
4
666
0
1
2
9