#P2304C. Cls, Orz is giving me a hard time

Cls, Orz is giving me a hard time

说明

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

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

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

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

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

输入格式

输入文件的第一行为 nn,表示测试数据的组数。

以下 nn 行,每行为一个 kk 值。

输出格式

输出包含nn行,每行输出一个对应的结果。

样例

样例输入1

1
7

样例输出1

13

样例解释1

小菜能够拿到的总实力值从小到大为 13491012131、3、4、9、10、12、13……,所以第 77 小的总实力值是 1313

提示

1n1001 \leq n \leq 100

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