马上就要到羊年了，羊村一片欢腾，懒羊羊则懒洋洋地躺在草坪上吃新年的巧克力棒。

他手上的巧克力棒是个由 n 个巧克力单元格组成的长度为 n 的长条，现在懒羊羊想把巧克力棒掰开成一个个小单元格。

初始时懒羊羊会把这根巧克力棒丢在草坪上，然后每次懒羊羊会从草坪上拿起一根长度大于 1 的巧克力棒，然后从某两个相邻的单元格的间隙处掰开变成两根巧克力棒，然后把这两根巧克力棒丢在草坪上。懒羊羊初始愉悦值为 0，每次掰开巧克力棒后如果这两根巧克力棒长度相等，那么懒羊羊将提升 1 点愉悦值。

当然，草坪上全是长度为 1 的巧克力棒时懒羊羊就会停止操作。现在懒羊羊想知道，他能获得的愉悦值最多是多少？

输入格式

一行一个正整数 T。

接下来 T 行，每行一个正整数 n 表示巧克力棒的长度，你需要对每个给出的 n 计算最多能获得的愉悦值。

输出格式

T 行每行一个整数，表示懒羊羊最多能获得的愉悦值。

样例一

input

output

explanation

对于 n=1，初始时草坪上已经全是长度为 1 的了，所以愉悦值为 0。

对于 n=3，懒羊羊可以先把它掰开变成一根长度为 1 的和一根长度为 2 的巧克力棒；然后再把长度为 2 的巧克力棒从正中间掰开获得 1 点愉悦值，所以答案是 1。

对于 n=4，懒羊羊可以先从正中间掰开变成两根长度为 2 的巧克力棒，获得 1 点愉悦值；然后再对于每根长度为 2 的巧克力棒从正中间掰开各获得 1 点愉悦值，所以答案是 3。

限制与约定

对于所有数据，T≤20。

时间限制：1