← 返回题目列表

Codeforces · 1362/C

C. 约翰尼和另一个评级下降

中文机器翻译题面 查看原题

在约翰尼最喜欢的竞争性编程平台上举行的最后一场比赛获得了相当积极的反响。然而,约翰尼的评分又下降了!他认为所提出的任务很可爱,但没有展示竞争对手技能的真相。

男孩现在正在查看以二进制系统写的连续参与者的评分。他认为,这样的评级差异越大,这些人挨在一起就越不公平。他将两个数字之间的差异定义为位位置的数量,其中一个数字为零,另一个数字为 1(我们假设数字用前导零填充到相同的长度)。例如,$$$5 = 101_2$$$ 和 $$$14 = 1110_2$$$ 之差等于 $$$3$$$,因为 $$$0101$$$ 和 $$$1110$$$ 在 $$$3$$$ 位置上不同。约翰尼将比赛的不公平性定义为相邻参与者的此类差异的总和。

约翰尼刚刚向您发送了评级序列,希望您找出比赛的不公平之处。您已经注意到,您有一个从 $$$0$$$ 到 $$$n$$$ 的连续整数序列。这很奇怪,但男孩固执地说一切都是对的。因此,请帮助他找到收到的数字所需的不公平性。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) - 测试用例的数量。以下 $$$t$$$ 行包含测试用例的描述。

每个测试用例中的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^{18})$$$。

输出

输出 $$$t$$$ 行。对于每个测试用例,您应该输出带有一个整数的单行 - 如果评级序列等于 $$$0$$$、$$$1$$$、...、$$$n - 1$$$、$$$n$$$,则比赛的不公平性。

示例

输入 #1

5
5
7
11
1
2000000000000

输出 #1

8
11
19
1
3999999999987

注意

对于 $$$n = 5$$$,我们计算以下序列的不公平性(从 $$$0$$$ 到 $$$5$$$ 的数字以二进制形式编写,并带有额外的前导零,因此它们都具有相同的长度):

- $$$000$$$
- $$$001$$$
- $$$010$$$
- $$$011$$$
- $$$100$$$
- $$$101$$$

差异分别等于$$$1$$$、$$$2$$$、$$$1$$$、$$$3$$$、$$$1$$$,因此不公平等于$$$1 + 2 + 1 + 3 + 1 = 8$$$。