题目描述

Fwb 可喜欢吃黑巧了。

Fwb 有一个专门用来装黑巧的盒子，但很不巧，今天盒子空了，Fwb 又该出去买点巧克力了。

由于 Fwb 也知道吃多了巧克力对身体不好，所以他决定他买的巧克力必须只能吃 $a$ 天，且不能多也不能少。

Fwb 吃巧克力是有规律的：他会在第一天吃一块巧克力，在品尝到巧克力的美味后，第二天吃两块巧克力，第 $i$ 天吃 $2^{i-1}$ 块巧克力（$i>0$）。

当剩余的巧克力不够一天吃的时候，Fwb 就会选择不吃；反之，当剩余的巧克力够一天吃的时候，Fwb 就一定会吃。

若在第 $i$ 天吃完的巧克力之后仍剩余 $k$ 颗，且 $k<2^i$，则 Fwb 会在第 $i+1$ 天再次吃 $1$ 颗，在第 $i+2$ 天再次吃 $2$ 颗，以此类推。换句话说，当 $k<2^i$ 时，第 $i+m$ 天会吃 $2^{m-1}$ 颗。

现在需要你求出，Fwb 在恰好吃 $a$ 天的前提下，最少需要购买多少颗巧克力。

输入格式

本题包含多组测试数据。

第一行输入一个正整数 $t$，表示数据组数。

接下来 $t$ 行，每行包含一个正整数 $a$，代表 Fwb 购买的巧克力需要恰好吃 $a$ 天。

输出格式

输出共 $t$ 行。对于每一个输入的 $a$，输出一个正整数代表 Fwb 至少需要购买的巧克力数量。

3
5
2
3

9
2
4

6
263
749
409
761
729
382

16760809
1095216660441
939524067
1099510579161
549755805658
503316452

提示

【样例 1 解释】

第一次询问：要求恰好 $5$ 天吃完，则买 $9$ 颗巧克力。安排如下：

• 第一天吃 $1$ 颗，剩余 $8$ 颗。
• 第二天吃 $2$ 颗，剩余 $6$ 颗。
• 第三天吃 $4$ 颗，剩余 $2$ 颗。
• 不够 $8$ 颗，第四天只能再从 $1$ 颗吃起，剩余 $1$ 颗。
• 不够 $2$ 颗，第五天只能再从 $1$ 颗吃起，吃 $1$ 颗，恰好吃完。

可以证明，没有更优的安排。

第二次询问：要求恰好两天吃完，买 $2$ 颗巧克力，每天 $1$ 颗即可。

第三次询问：要求恰好三天吃完，买 $4$ 颗巧克力，每天分别吃 $1,2,1$ 颗。

【数据范围】

对于 $30\%$ 的数据，$1\le a\le 10$。

对于 $100\%$ 的数据，$1\le t,a\le 1000$。

保证答案在 $long\ long$ 范围内。