CF1362C.Johnny and Another Rating Drop

The last contest held on Johnny's favorite competitive programming platform has been received rather positively. However, Johnny's rating has dropped again! He thinks that the presented tasks are lovely, but don't show the truth about competitors' skills.

The boy is now looking at the ratings of consecutive participants written in a binary system. He thinks that the more such ratings differ, the more unfair is that such people are next to each other. He defines the difference between two numbers as the number of bit positions, where one number has zero, and another has one (we suppose that numbers are padded with leading zeros to the same length). For example, the difference of $5 = 101_2$ and $14 = 1110_2$ equals to $3$, since $0101$ and $1110$ differ in $3$ positions. Johnny defines the unfairness of the contest as the sum of such differences counted for neighboring participants.

Johnny has just sent you the rating sequence and wants you to find the unfairness of the competition. You have noticed that you've got a sequence of consecutive integers from $0$ to $n$. That's strange, but the boy stubbornly says that everything is right. So help him and find the desired unfairness for received numbers.

最近在 Johnny 最喜欢的编程竞赛平台上举办的上一场比赛获得了相当积极的评价。然而，Johnny 的评分（rating）再次下降了！他认为题目本身非常出色，但却无法真实反映参赛者的真实水平。

现在，Johnny 正在查看连续参赛者的评分，这些评分以二进制形式给出。他认为：两个相邻参赛者的评分二进制表示差异越大，将他们排在一起就越不公平。他将两个数之间的“差异”定义为：在相同长度（高位补零对齐后）的二进制表示下，一个数该位为 0 而另一个数该位为 1 的位置个数。例如，$5 = 101_2$ 与 $14 = 1110_2$ 的差异为 $3$，因为将它们补零至等长后得到 $0101$ 和 $1110$，二者在 $3$ 个位置上满足上述条件。Johnny 将整场比赛的“不公平度”（unfairness）定义为：所有相邻参赛者评分对之间差异值的总和。

Johnny 刚刚把评分序列发给了你，希望你帮他计算这场比赛的不公平度。你注意到，收到的序列恰好是 $0$ 到 $n$ 的连续整数。这看起来有些奇怪，但 Johnny 坚持认为一切无误。因此，请你帮他计算所给数字序列对应的不公平度。

The input consists of multiple test cases. The first line contains one integer $t$ ($1 \leq t \leq 10\,000$) — the number of test cases. The following $t$ lines contain a description of test cases.

The first and only line in each test case contains a single integer $n$ ($1 \leq n \leq 10^{18})$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10\,000$），表示测试用例的数量。接下来的 $t$ 行描述了各个测试用例。

每个测试用例仅有一行，包含一个整数 $n$（$1 \leq n \leq 10^{18}$）。

Output $t$ lines. For each test case, you should output a single line with one integer — the unfairness of the contest if the rating sequence equals to $0$, $1$, ..., $n - 1$, $n$.

输出 $t$ 行。对于每个测试用例，您应在一行中输出一个整数——即当评分为序列 $0$, $1$, ..., $n - 1$, $n$ 时，比赛的不公平度。

For $n = 5$ we calculate unfairness of the following sequence (numbers from $0$ to $5$ written in binary with extra leading zeroes, so they all have the same length):

• $000$
• $001$
• $010$
• $011$
• $100$
• $101$

The differences are equal to $1$, $2$, $1$, $3$, $1$ respectively, so unfairness is equal to $1 + 2 + 1 + 3 + 1 = 8$.

当 $n = 5$ 时，我们计算如下序列的不公平度（将 $0$ 到 $5$ 的数字以二进制形式写出，并在前面补零，使它们长度相同）：

• $000$
• $001$
• $010$
• $011$
• $100$
• $101$

相邻两项的差值分别为 $1$、$2$、$1$、$3$、$1$，因此不公平度为 $1 + 2 + 1 + 3 + 1 = 8$。