说明

初入103，小菜就对 Orz 队霸的位置有所觊觎。Orz 想给小菜一个下马威，当时他正准备招纳新生，于是乎，Orz 就让小菜去替他去招纳新生。

小菜宣讲后，有很多的新生找到小菜想要入队，假设每名新生的编号依次为 $1、2、3、……$，我们认为第 $i$ 名同学的实力值为 $3^{i-1}$。

Orz 需要小菜为他招收任意名新生，而小菜选中的新生有一个“总实力值”，即为新生们的实力值之和。

举个例子：小菜这一次招收了第一名新生和第三名新生，那么他们的“总实力值”为 1+9=10。

Orz 想知道，他可以获得的第 $k$ 小的“总实力值”是多少。众所周知小菜啥也不会，只会那问题来为难你，因此正义的你请帮助我们的可怜的小菜告诉 Orz 这个第 $k$ 小的“总实力值”。

输入格式

输入文件的第一行为 $n$，表示测试数据的组数。

以下 $n$ 行，每行为一个 $k$ 值。

输出格式

输出包含$n$行，每行输出一个对应的结果。

样例

样例输入1

1
7

样例输出1

13

样例解释1

小菜能够拿到的总实力值从小到大为 $1、3、4、9、10、12、13……$，所以第 $7$ 小的总实力值是 $13$。

提示

$1 \leq n \leq 100$

$1 \leq k \leq 2^{31}-1$