Description

Kenny 的厨房里有一个微波炉。这个微波炉有一个非常奇怪的单按钮定时器界面。

当你把食物放进微波炉并想要开始加热时，你需要按下按钮一次或多次。当你第一次按下按钮时，定时器会被设置为 $1$ 分钟。如果你立刻再次按下按钮，定时器会再增加 $2$ 分钟，总共变为 $3$ 分钟。如果你再次立刻按下按钮，则会再增加 $4$ 分钟，以此类推。如果你连续第 $k$ 次按下按钮，定时器会增加 $2^k$ 分钟。

看起来有些时间是无法通过这种方式设置的，比如说，如何设置 $2$ 分钟？幸运的是，你可以通过暂停一秒来重置按钮计数器。例如，如果你按一次按钮，暂停一秒，然后再按一次按钮，定时器就会被设置为 $2$ 分钟。再比如：如果你按、按、暂停、按、按、按，那么定时器上的总时间就是 $1+2+1+2+4=10$ 分钟。

Kenny 需要将食物加热恰好 $x$ 分钟。请你帮他计算，设置定时器为 $x$ 分钟时，最少需要多少次一秒的暂停。假设只有暂停会消耗时间，按按钮的时间可以忽略不计。

Input Format

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来每组测试数据包含一行，一个整数 $x$，表示 Kenny 需要加热的分钟数（$1 \le x \le 10^{18}$）。

Output Format

对于每组测试数据，输出一个整数，表示设置微波炉定时器为 $x$ 分钟时，所需的最少一秒暂停次数。

7
1
2
3
4
10
239
123456789012

0
1
0
1
1
4
19

Hint

在第一个样例测试中，不需要暂停：Kenny 只需按一次按钮即可。

在第二个样例测试中，Kenny 可以按一下，暂停，再按一下，将定时器设置为 $2$ 分钟。

在第三个样例测试中，Kenny 只需连续按两次按钮即可设置 $3$ 分钟。

在第四个样例测试中，Kenny 可以按、按、暂停、按，将定时器设置为 $1+2+1=4$ 分钟。

由 ChatGPT 4.1 翻译