题目背景

AzureHair 在 NOIP 2022 中被喵了个喵创死，于是患上了不治之症——T2 恐惧症，于是他在 NOIP 2023 中果断跳过了 T2 并杠 T3 两小时无果，遗憾离场，他的同学决定帮他治疗这种不治之症。

在他的同学给他治愈了 T2 恐惧症后，他自信的开始了他的 SDOI，遂分讨写了 $2$ 个小时没写出来，遗憾离场……

题目描述

AzureHair 的同学把 AzureHair 和 $n$ 只猫猫关在一个房间里，并且要求 AzureHair 每过一天就交出 $\frac{n}{2}$ 只猫猫，但是如果 $n$ 是奇数时，AzureHair 就会纠结于要交出 $\frac{n+1}{2}$ 只猫猫还是交出 $\frac{n-1}{2}$ 只猫猫。AzureHair 不想让自己纠结，所以请你计算出直到所有猫猫都被拿出房间时，AzureHair 的最小纠结次数是多少。

输入格式

本题有多组测试数据。

第一行一个整数 $T$。

接下来 $T$ 行，每行一个整数 $n$。

输出格式

$T$ 行，每行一个整数表示最小纠结次数。

2
13
7

3
2

提示

【样例解释】

对于 $13$ 只猫猫，只纠结 $3$ 次的过程如下：

选择交出 $7$ 只猫猫，剩余 $6$ 只；

不纠结，交出 $3$ 只猫猫，剩余 $3$ 只；

选择交出 $2$ 只猫猫，剩余 $1$ 只；

选择交出 $1$ 只猫猫，所有猫猫均被取走。

容易证明不存在少于 $3$ 次纠结的方案。

【数据范围】

对于 $10\%$ 的数据，保证 $1\le n \le 10$。

对于 $30\%$ 的数据，保证 $1\le n \le 10^{5}$。

对于 $100\%$ 的数据，保证 $1\le n \le 2^{60}$，$1 \le T \le 5\times 10^5$。