问题描述

猫猫是丛林里很多动物（除了 @）心中的天使，她为此十分自豪。猫猫最爱吃 @ 了，她每天都要去池塘钓 @ 吃。猫猫经常吃 @ 的脑，数学特别强，然而，小女生的性格决定了她的贪玩。

一天，猫猫钓到了很多条 @ 。她并不想马上就把可怜的 @ 吃掉，而是先折磨够之后再吃（有句话叫什么来着～最毒不过猫猫心）。

猫猫将这很多很多（数不过来）条 @ 按照外观的漂亮程度排序，每个 @ 的编号依次为 $1、2、3……N$，第 $i$ 条 @ 的美观程度为 $3^{(i-1)}$。

猫猫要把这些 @ 放到桶里去。她每次拿的 @ 的数目是任意的。 @ 的“总美观程度”为各条 @ 美观程度之和。例如：猫猫这一次拿了第一条 @ 和第三条 @ ，那么美观程度为 $1+9=10$。

猫猫想知道，她可以获得的第k大的“总美观程度”是多少。

读入 $k$，输出猫猫能够获得的，第 $k$ 大的“总美观程度”。

输入格式

数据包含 $n+1$ 行，第一行读入 $n(n\leq 100)$。

以下 $n$ 行每行包含一个 $k$。

输出格式

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

1
7

13

样例解释

猫猫能够拿到的美观程度从小到大为 $1、3、4、9、10、12、13……$，所以第7大的美观程度是 $13$。

数据范围

对于 $50\%$ 的输入文件，有 $k≤5000$。

对于 $100\%$ 的输入文件，有 $k≤2^{63}-1$。