C. 词典（dictionary）

一个 01 串 $s$ 是单词当且仅当 $s$ 中不包含两个连续的 $0$。

一个包含 $n$ 个单词的词典是 $n$ 个单词的集合，且满足其中任意一个单词都不是任意其他单词的前缀。

给定一个词典 $D$，定义 01 串 $s$ 的代价

$C(s)=\sum_{j=1}^{k}\lfloor 1+\log_2 j\rfloor$，

其中 $k$ 是 $D$ 中满足 $s$ 是 $t$ 的前缀的单词 $t$ 的数量。该词典 $D$ 的代价即为所有 01 串的代价之和。

例如，考虑一个包含 $4$ 个单词的词典 $\{0,10,110,111\}$。这个词典的代价为

$C(\epsilon)+C(0)+C(1)+C(10)+C(11)+C(110)+C(111)=8+1+5+1+3+1+1=20$。

这里 $\epsilon$ 表示空串。

求包含 $n$ 个单词的词典的代价的最小值。

输入格式

第一行一个整数 $t$（$1\le t\le 50000$），表示数据组数。

接下来 $t$ 行每行一个整数 $n$（$2\le n\le 10^{15}$），表示词典包含的单词数量。

输出格式

对于每组数据输出一个整数表示答案。

样例

样例输入

6
2
4
10
5000
114514
1000000000000000

样例输出

5
20
98
507842
21880717
1738413860843500846

子任务

• Subtask 1（10 points）： $n\le 5000$。
• Subtask 2（30 points）： $n\le 500000$。
• Subtask 2（10 points）： $n\le 30000000$。
• Subtask 3（50 points）： 无额外限制。