1416. 选数

假设有无穷数列,其通项公式为 ai=3i1a_i=3^{i-1}

现从数列中任意选取若干个数并求和得到一个数 SS

问所有选取方案中第 kk 小的 SS 是多少。

输入

多组输入。

第一行一个整数 T (1T50)T \ (1 \leq T \leq 50)TT 组测试样例。

之后的 TT 行中,每一行有一个数字 k (1k2311)k \ (1 \leq k \leq 2^{31}-1)

输出

每一个测试样例,输出一行一个整数,表示答案。

样例

标准输入 复制文本
2
7
4
标准输出 复制文本
13
9

提示

可能的 SS 的取值从小到大排为 1,3,4 (=1+3),9,10 (=1+9),12 (=9+3),13 (=1+9+3)...1,3,4 \ (=1+3), 9,10 \ (=1+9), 12 \ (=9+3), 13\ (=1+9+3)...,第 77 小为 1313,第 44 小为 99.

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 7
通过 6