Vanya 非常喜欢数学。有一天,当他解决另一道数学问题时,他想到了一棵有趣的树。这棵树的构建如下。
最初,树只有一个编号为 $$$1$$$ 的顶点 — 树的根。然后,Vanya 将两个子项添加到其中,并为它们分配连续的数字 - 分别为 $$$2$$$ 和 $$$3$$$。之后,他将从 $$$2$$$ 开始按编号递增的顺序将子节点添加到顶点,并为它们的子节点分配最小未使用的索引。这样一来,Vanya 将得到一棵无限树,其根位于顶点 $$$1$$$,其中每个顶点将恰好有两个子节点,并且顶点编号将按层顺序排列。
Vanya 树的一部分。
Vanya 想知道这样一棵树中从编号为 $$$1$$$ 的顶点到编号为 $$$n$$$ 的顶点的路径上的顶点编号之和等于多少。由于瓦尼娅不喜欢数数,他请你帮他求这个和。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
接下来是 $$$t$$$ 行——测试用例的描述。每行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^{16}$$$) - Vanya 要计算从根到该顶点的路径上的顶点数总和的顶点数。
输出
对于每个测试用例,打印一个整数 - 所需的总和。
示例
输入 #1
6 3 10 37 1 10000000000000000 15
输出 #1
4 18 71 1 19999999999999980 26
注意
在示例的第一个测试用例中,从根到顶点 $$$3$$$ 的路径上有两个顶点 $$$1$$$ 和 $$$3$$$,它们的总和等于 $$$4$$$。
在示例的第二个测试用例中,从根到编号为 $$$10$$$ 的顶点的路径上有顶点 $$$1$$$、$$$2$$$、$$$5$$$、$$$10$$$,它们的编号之和等于 $$$1+2+5+10 = 18$$$。