题目描述

Vanya 非常喜欢数学。一天，当他在解一道数学题时，想到了一个有趣的树。这棵树的构造如下：

最初，树中只有一个编号为 $1$ 的结点——也就是树根。然后，Vanya 给它添加两个子节点，分别赋予连续的编号 $2$ 和 $3$。接下来，他会按照结点编号从小到大的顺序，从 $2$ 开始，依次为每个结点添加两个子节点，并赋予它们当前未使用的最小编号。最终，Vanya 会得到一棵以 $1$ 为根的无限二叉树，每个结点恰好有两个子节点，结点编号按层次顺序依次排列。

Vanya 想知道，在这样一棵树中，从编号为 $1$ 的结点到编号为 $n$ 的结点的路径上，所有结点编号之和是多少。由于 Vanya 不喜欢计算，他请求你帮他求出这个和。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

接下来有 $t$ 行，每行包含一个整数 $n$（$1 \le n \le 10^{16}$），表示 Vanya 想要计算从根到编号为 $n$ 的结点路径上所有结点编号之和。

输出格式

对于每个测试用例，输出一个整数，表示所求的路径上所有结点编号之和。

说明/提示

在第一个样例中，从根到编号为 $3$ 的结点路径上有结点 $1$ 和 $3$，它们的和为 $4$。

在第二个样例中，从根到编号为 $10$ 的结点路径上有结点 $1$、$2$、$5$、$10$，它们的和为 $1+2+5+10=18$。

由 ChatGPT 4.1 翻译

样例

6
3
10
37
1
10000000000000000
15

4
18
71
1
19999999999999980
26