#P3005. 小胖寻路

小胖寻路

说明

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

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

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

二叉树1.png

输入格式

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

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

1T1031 \le T \le 10^31x 1031 \le x  \le 10^3

输出格式

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

样例

样例输入 1

4
1
2
4
666

样例输出 1

0
1
2
9