题目描述

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

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

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

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

1. 生成功能：徐老师可以凭空生成一个质量为 1 的羊腿，并将它放在装置最顶层

2. 合成功能：徐老师可以将现在处于最顶层的两个羊腿合并成一个羊腿，并且羊腿质量不会发生消耗，并将合成后的 羊腿放在装置最顶层

3. 复制功能：徐老师可以将现在处于最顶层的羊腿完美复制一份，并将它放在装置最顶层

例如徐老师可以依次使用如下按钮： 生成、生成、合成、复制、生成、合成、合成 这样的操作可以凭空得到一个质量为 5 的羊腿 假设三种功能的能量消耗均一样，现在徐老师想知道最少需要使用多少次功能，可以凭空得到一个质量为 n 的羊腿？并且徐老师不想浪费粮食，他不希望最终装置中还存在其他羊腿

输入格式

输入第一行包含一个整数 T , 表示询问次数 每行包含一个正整数 n,表示徐老师想要得到的羊腿质量

输出格式

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

样例输入

1 5

样例输出

7

数据范围及提示

1 <= n <= 100 1 <= T <= 1000