1416. 选数

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

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

问所有选取方案中第 k 小的 S 是多少。

输入

多组输入。

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

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

输出

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

样例

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

提示

可能的 S 的取值从小到大排为 1,3,4 \ (=1+3), 9,10 \ (=1+9), 12 \ (=9+3), 13\ (=1+9+3)...,第 7 小为 13,第 4 小为 9.

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