题目描述

猫猫是丛林里很多动物心中的天使，她为此十分自豪。猫猫最爱吃鱼了，她每天都要去池塘钓鱼吃。猫猫经常吃鱼脑，数学特别强，然而，小女生的性格决定了她的贪玩。一天，猫猫钓到了很多条鱼。她并不想马上就把可怜的鱼儿吃掉，而是先折玩够之后再吃。 猫猫将这很多很多（数不过来）条鱼按照外观的漂亮程度排序，每个鱼的编号依次为$\red {1、2、3……N}$，第$\red i$条鱼的美观程度为$\red {3^{(i-1)}}$。 猫猫要把这些鱼放到桶里去。她每次拿的鱼的数目是任意的。其中的鱼的“总美观程度”为各条鱼美观程度之和。例如：猫猫这一次拿了第一条鱼和第三条鱼，那么美观程度为$\red {1+9=10}$。猫猫想知道，她可以获得的第$\red {k}$大的“总美观程度”是多少。从文件中读入$\red {k}$，输出猫猫能够获得的，第$\red {k}$大的“总美观程度”。

输入格式

数据包含$\red {n+1}$行，第一行读入$\red {n(n≤100)}$。以下$\red {n}$行每行包含一个$\red {k(k<=1000)}$。

输出格式

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

样例

输入样例

1
7

输出样例

13

提示

猫猫能够拿到的美观程度从小到大为$\red {1、3、4、9、10、12、13……}$所以第$\red {7}$大的美观程度是$\red {13}$。对于$\red {50\%}$的输入文件，有$\red {k≤5000}$。对于$\red {100\%}$的输入文件，有$\red {k≤2^{31}-1}$