文件读写

输入文件copy.in

输出文件copy.out

限制

1000ms

128MB

说明

苏老师有一个用于存放羊腿的神奇装置，这个装置呈一个桶的形状，深度无限大，其中每一层都可以存放一个羊腿

每次苏老师往桶里放入羊腿时，只能放在最顶层羊腿的更上一层，而每次取出羊腿时也只能取出最顶层的羊腿

例如苏老师的桶里依次存放了 $3$ 个羊腿，质量分别为 $1,2,3$，那么此时苏老师只能取出最顶层质量为 $3$ 的羊腿，不能跨过 $3$ 直接取质量为 $2$ 和 $1$ 的羊腿

现在苏老师给这个装置加了三个更加神奇的功能——生成、合成与复制！

1. 生成功能：苏老师可以凭空生成一个质量为 $1$ 的羊腿，并将它放在装置最顶层
2. 合成功能：苏老师可以将现在处于最顶层的两个羊腿合并成一个羊腿，并且羊腿质量不会发生消耗，并将合成后的羊腿放在装置最顶层
3. 复制功能：苏老师可以将现在处于最顶层的羊腿完美复制一份，并将它放在装置最顶层

例如苏老师可以依次使用如下按钮：`生成、生成、合成、复制、生成、合成、合成`

这样的操作可以凭空得到一个质量为 $5$ 的羊腿

假设三种功能的能量消耗均一样，现在苏老师想知道最少需要使用多少次功能，可以凭空得到一个质量为 $n$ 的羊腿？

并且苏老师不想浪费粮食，他不希望最终装置中还存在其他羊腿

输入格式

输入第一行包含一个整数 $T$, 表示询问次数

每行包含一个正整数 $n$,表示苏老师想要得到的羊腿质量

| 数据组号 | $n$      | 特别的保证| |
| :---: | :---: | :---: | :---: |
| $1$        | $1 \leq n \leq 10$    |无    | $T=1$ |
| $2$       | $1 \leq n \leq 15$    | 无 | $T = 5$ | 
| $3 \sim 5$        | $1 \leq n \leq 100$ | 无 |  $T \leq 1000$ |

输出格式

对于每一次询问，输出苏老师最少需要使用功能的次数

样例

1
5

7