微波炉定时器

题目描述

Y 同学家的微波炉有一个特殊的单按钮定时器。

设置时间的操作规则如下：

• 你可以进行一次或多次连续按压操作。
• 每次“连续按压”包含一系列不间断的按钮点击。
• 在一次“连续按压”中，第 $k$ 次点击（$k \ge 1$）会使定时器的时间增加 $2^{k-1}$ 分钟。
  • 例如：点击 1 次，增加 $1$ 分钟（总计 $1$ 分钟）。
  • 点击 2 次，增加 $1+2=3$ 分钟。
  • 点击 3 次，增加 $1+2+4=7$ 分钟。
  • 一般地，进行 $L$ 次点击将产生 $\sum_{i=0}^{L-1} 2^i = 2^L - 1$ 分钟的时间增量。
• 你可以通过暂停一秒来结束当前的“连续按压”并重置点击计数器，从而开始下一次“连续按压”。
• 定时器的最终时间是所有“连续按压”所产生时间的总和。

Y 同学需要将定时器恰好设置为 $x$ 分钟。请你计算，为了达到这个目标，他最少需要暂停多少次？（注：第一次“连续按压”之前不需要暂停）。

输入格式

第一行包含一个整数 $T$，表示测试数据的组数。

接下来 $T$ 行，每行包含一个整数 $x$，表示目标时间。

输出格式

对于每组测试数据，输出一行一个整数，表示最少的暂停次数。

样例

样例输入 #1

7
1
2
3
4
10
239
123456789012

样例输出 #1

0
1
0
1
1
4
19

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le T \le 10^4$
• $1 \le x \le 10^{18}$