题目内容

在一种特殊的整数运算系统中，任何正整数 $x$ 都能进行“比特消除”操作。定义 $x$ 的最低有效位值 $\operatorname{lowbit}(x) = (x)\ ext{and}\ (-x)$，即 $x$ 的二进制表示中最低位 $1$ 所对应的数值。一次消除的过程为：$x$ 变为 $x - \operatorname{lowbit}(x)$，同时产生代价 $\operatorname{lowbit}(x) - 1$。消除可以不断进行，直到 $x$ 变为 $0$ 为止。

对于一个初始值为 $x$ 的整数，其总代价 $G(x)$ 定义为初始值 $x$ 与过程中每一次消除产生的代价的按位或结果。形式化地，若消除序列中产生的代价依次为 $c_1, c_2, \dots, c_k$，则 $G(x) = x \ ext{or}\ c_1 \ ext{or}\ c_2 \ ext{or}\ \dots \ ext{or}\ c_k$。

给定一个上界 $n$，请你计算 $1$ 到 $n$ 中所有正整数的总代价之和，即 $\sum_{i=1}^{n} G(i)$。

约束条件：测试数据组数 $T$ 不超过 $2 imes 10^5$，上界 $n$ 满足 $1 \le n \le 10^9$。