假设有无穷数列,其通项公式为 ai=3i−1a_i=3^{i-1}ai=3i−1。
现从数列中任意选取若干个数并求和得到一个数 SSS。
问所有选取方案中第 kkk 小的 SSS 是多少。
输入
多组输入。
第一行一个整数 T (1≤T≤50)T \ (1 \leq T \leq 50)T (1≤T≤50),TTT 组测试样例。
之后的 TTT 行中,每一行有一个数字 k (1≤k≤231−1)k \ (1 \leq k \leq 2^{31}-1)k (1≤k≤231−1)。
输出
每一个测试样例,输出一行一个整数,表示答案。
样例
2 7 4
13 9
提示
可能的 SSS 的取值从小到大排为 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)...1,3,4 (=1+3),9,10 (=1+9),12 (=9+3),13 (=1+9+3)...,第 777 小为 131313,第 444 小为 999.