### 问题描述 在一个宁静的夜晚，小蓝在梦中来到了一个神秘的森林。这个森林不同寻常，它由无数棵奇特的树木构成，每棵树都有其独特的编号。最为奇特的是，森林中的每棵树都遵循一个特别的规则生长。 森林中最初只有一棵编号为 $1$ 的树，即森林的源头。然后，源头树分裂出两棵新的树，它们的编号分别是连续的 $2$ 和 $3$。接着，源头树将按照新树的编号递增的顺序分裂出更多的子树，每棵新树的编号都是未使用过的最小编号。 结果，小蓝发现这个神秘的森林其实是一个无穷大的树状结构，每棵树都恰好有两棵子树，而且树的编号是按层次顺序排列的。 在这个神秘的森林中，小蓝想知道从编号为 $1$ 的源头树到编号为 $n$ 的树所经过的所有树的编号之和是多少。 由于森林非常庞大，小蓝无法全部探索，所以他希望你能帮助他找出这个编号之和。 ### 输入格式 第一行包含一个整数 $t$，表示小蓝想要探索的路径数量。 接下来 $t$ 行，每行包含一个整数 $n$，表示小蓝想要探索的路径终点树的编号。 数据范围保证：$1 \leq t \leq 10^3$，$1 \leq n \leq 10^{16}$。 ### 输出格式 对于每个测试用例，输出一个整数，表示从源头树到终点树所经过的所有树的编号之和。 ### 样例输入 ```markdown 2 2 5 ``` ### 样例输出 ```markdown 3 8 ``` ### 说明 对于描述的前三层节点如下图所示，对于样例到达点 $2$ 的路径和为 $3$，到达点 $5$ 的路径和为 $8$。