Kenny 家里的微波炉有一个非常奇怪的单键定时器接口。

当你把食物放进微波炉并想要开始加热时，你需要按一次或多次按钮。当你第一次按下按钮时，定时器被设置为 1 分钟。如果你立即再次按下按钮，定时器会增加 2 分钟，总共 3 分钟。如果你再次立即按下按钮，定时器会再增加 4 分钟，以此类推。如果你在没有暂停的情况下第 $k$ 次按下按钮，它会为定时器增加 $2^{k-1}$ 分钟。

看起来通过使用这个按钮似乎无法设置某些时间段：例如，如何将定时器设置为 2 分钟？幸运的是，你可以通过暂停一秒钟来重置按钮计数器。例如，如果你按下按钮，暂停一秒钟，然后再按一次按钮，定时器就会被设置为 2 分钟。另一个例子：如果你按、按、暂停、按、按、按，定时器上的总时间为 $1 + 2 + 1 + 2 + 4 = 10$ 分钟。

Kenny 需要加热食物恰好 $x$ 分钟。请帮他找出设置定时器所需的最少一秒钟暂停次数。假设只有暂停需要时间，而按下按钮的时间忽略不计。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。

接下来是各测试用例的描述。

每个测试用例仅包含一行，为一个整数 $x$，表示 Kenny 加热食物所需的分钟数 ($1 \le x \le 10^{18}$)。

输出格式

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

样例

输入 1

7
1
2
3
4
10
239
123456789012

输出 1

0
1
0
1
1
4
19

说明

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

在第二个测试用例中，Kenny 可以通过按、暂停、按来将定时器设置为 2 分钟。

在第三个测试用例中，Kenny 只需按两次按钮即可将定时器设置为 3 分钟。

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