CF1843C.Sum in Binary Tree

Vanya really likes math. One day when he was solving another math problem, he came up with an interesting tree. This tree is built as follows.

Initially, the tree has only one vertex with the number $1$ — the root of the tree. Then, Vanya adds two children to it, assigning them consecutive numbers — $2$ and $3$, respectively. After that, he will add children to the vertices in increasing order of their numbers, starting from $2$, assigning their children the minimum unused indices. As a result, Vanya will have an infinite tree with the root in the vertex $1$, where each vertex will have exactly two children, and the vertex numbers will be arranged sequentially by layers.

Part of Vanya's tree.

Vanya wondered what the sum of the vertex numbers on the path from the vertex with number $1$ to the vertex with number $n$ in such a tree is equal to. Since Vanya doesn't like counting, he asked you to help him find this sum.

瓦尼亚非常喜欢数学。一天，当他正在解决另一道数学题时，他构思出了一棵有趣的树。这棵树的构建方式如下：

最初，树中只有一个编号为 $1$ 的顶点——即树的根节点。接着，瓦尼亚为其添加两个子节点，并依次赋予它们连续的编号：$2$ 和 $3$。此后，他将按顶点编号递增的顺序（从 $2$ 开始）依次为各顶点添加子节点，并为其子节点分配当前尚未使用的最小编号。最终，瓦尼亚得到一棵以顶点 $1$ 为根的无限树，其中每个顶点恰好有两个子节点，且顶点编号按层序逐层连续排列。

瓦尼亚树的一部分。

瓦尼亚好奇：在这棵树中，从编号为 $1$ 的顶点到编号为 $n$ 的顶点的路径上，所有顶点编号之和是多少？由于瓦尼亚不喜欢手动计算，他请你帮忙求出这个和。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

This is followed by $t$ lines — the description of the test cases. Each line contains one integer $n$ ($1 \le n \le 10^{16}$) — the number of vertex for which Vanya wants to count the sum of vertex numbers on the path from the root to that vertex.

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

接下来是 $t$ 行，描述各测试用例。每行包含一个整数 $n$（$1 \le n \le 10^{16}$）—— Vanya 想要求从根节点到该顶点的路径上所有顶点编号之和的顶点编号。

For each test case, print one integer — the desired sum.

对于每个测试用例，输出一个整数——即所求的和。

In the first test case of example on the path from the root to the vertex $3$ there are two vertices $1$ and $3$, their sum equals $4$.

In the second test case of example on the path from the root to the vertex with number $10$ there are vertices $1$, $2$, $5$, $10$, sum of their numbers equals $1+2+5+10 = 18$.

在示例的第一个测试用例中，从根节点到顶点 $3$ 的路径上包含两个顶点 $1$ 和 $3$，它们的编号之和为 $4$。

在示例的第二个测试用例中，从根节点到编号为 $10$ 的顶点的路径上包含顶点 $1$、$2$、$5$、$10$，它们的编号之和为 $1+2+5+10 = 18$。