假设有无穷数列，其通项公式为 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.