你听说过著名的 Dedenne 天线吗？它们使得 Dedenne 即使相隔万里也能互相交流。然而，它们怀疑自己的交流方式并非最优。这就是为什么 Dedenne 来找你，希望你能优化它们的语言。

Dedenne 使用的语言包含 $n$ 个单词。为了传输一个单词，Dedenne 必须首先使用它们记忆的字典将该单词转换为一个非空的二进制字符串（码字），然后传输该字符串。接收方收到序列后，使用相同的字典恢复出单词。为了保证传输的正确性，字典中的任意两个码字不能相等，且没有任何一个字符串是另一个字符串的前缀。

由于 Dedenne 的特殊性质，码字中不允许出现连续的两个 $0$ 位——当传输时，它们会合并成 $1$ 并导致发射机无限期挂起。

显然，记忆字典是一件非常痛苦的事情。形式化地讲，设 $C(s)$ 为任意二进制字符串 $s$ 的代价，若 $s$ 是恰好 $k$ 个码字的前缀，则 $C(s) = \sum_{j=1}^k \lfloor 1 + \log_2 j \rfloor$。那么，记忆字典的总代价等于所有作为至少一个码字前缀的二进制字符串 $s$ 的 $C(s)$ 之和。

例如，考虑包含 4 个码字的字典：$0, 10, 110, 111$。 我们可以看到记忆该字典的代价等于 $C(\varepsilon) + C(0) + C(1) + C(10) + C(11) + C(110) + C(111) = 8 + 1 + 5 + 1 + 3 + 1 + 1 = 20$。注意 $\varepsilon$ 表示空字符串。

现在你大概知道 Dedenne 想要什么了。记忆 $n$ 个单词的字典的最小代价是多少？

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 50\,000$)，表示独立测试用例的数量。接下来的 $t$ 行，每行包含一个整数 $n$ ($2 \le n \le 10^{15}$)，表示 Dedenne 需要记忆的单词数量。

输出格式

对于每个测试用例，输出一个整数，表示 Dedenne 可以实现的包含 $n$ 个单词的字典的最小代价。

样例

输入 1

3
2
4
10

输出 1

5
20
98

说明

下图展示了当 $n = 10$ 时，Dedenne 可能使用的一种最小化记忆代价的字典：