The Site of Sunrin

Standing tall on high Namsan

(omitted)

Build it upon bedrock

the site of Sunrin

In 1899, you receive a decree from Emperor Gojong of the Korean Empire and must choose the site on which to build the Government School of Industry and Commerce, Korea's first vocational education institution.

The Korean Empire has several sites suitable for building a school, and each site has a distinct natural number as its number. In particular, the number of the site of Sunrin is a natural number obtained by adding at most one natural number of the form $3^k$ for each $k \ge 0$. That is, the numbers of the site of Sunrin include $1(=3^0), 3(=3^1), 9(=3^2), 27(=3^3), 81(=3^4), 90(=3^2+3^4), 91(=3^0+3^2+3^4)$, and so on.

You have been ordered to find the $N$-th smallest site of Sunrin. Write a program that finds the $N$-th site of Sunrin.

The first line gives $T$, the number of sites of Sunrin you must find.

Each of the next $T$ lines gives $N$, the information about one site of Sunrin you must find.

Print the numbers of the sites of Sunrin you must find, one per line, in order.

$1 \leq T \leq 1\,000$

$1 \leq N \leq 123\,456\,789\,123$

The numbers in the input and the answers you must print are very large, so you need a 64-bit type (long long in C/C++, long in Java, printed with %lld).