题解

题面描述

给定正整数 $n$ ，定义对每个整数 $x$ 的“退化运算”：

小美有一些运算：她定义一个整数 $x$ 的退化运算 $Back_x$ 为自己按位与自己的负数，形式化的说， $Back_x=(x)and(-x)$ ；一次成功的退化后， $x$ 变为 $x-Back_x$ ；消耗为 $max$ { $0,Back_x-1$ } 。

退化是可以持续的进行的，例如，当 $x=37$ 时：

第一次退化， $x=37$ ， $Back_{37}=(37)and(-37)=1$ ，退化为 $37-Back_{37}=36$ ，消耗 $0$ ；
在刚刚的基础上进行第二次退化， $x=36,Back_{36}=(36)and(-36)=4$ ，退化为 $36-Back_{36}=32$ ，消耗 $3$ ；
在刚刚的基础上进行第三次退化， $x=32$ , ......
......

我们记数字 $x$ 退化过程中的总消耗 $Cost_x$ 为：初始的 $x$ 与每一次退化的消耗按位或后得到的结果。

例如 $Cost_{37}=37$ $or$ $0$ $or$ $3$ $or$ $···$ 。

现在，你已经完全掌握小美的运算了，你需要计算的是， $1$ ~ $n$ 中，全部数字退化总消耗之和，即

$\sum_{i=1}^{n}Cost_i$ 。

每个测试文件均包含多组测试数据，第一行输入一个整数 $T(1≦T≦2×10^5)$ 代表数据组数，每组测试数据描述如下：

在一行上输入一个整数 $n(1 ≦n≦ 10^9)$ 代表运算的上界。

对于每一组测试数据，在同一行上连续输出一个整数，代表 $1$ ~ $n$ 中，全部数字退化总消耗之和。

输入

输出

1 4 7 14 981396131

说明

$Cost_1=1,Cost_2=3,Cost_3=3,Cost_4=7$ 。