Description

Grahc is playing a game called "Gokémon Po" and he has caught a lot of "Gokémon". Every type of Pokémon has a unique positive integer as its ID. Grahc found that there exists a special item that can transform one type of Gokémon into another type of a strictly larger ID, with the result only depending on its original ID. In other words, there exists a function $f$, if the original ID of the Gokémon is $x$, the ID of the Gokémon after transformation will be $f(x)$.

After several trials, Grahc found that if he uses the item twice in a row on a Gokémon of ID $x$, it will be transformed into a Gokémon of ID $3x$, no matter what $x$ is.

Grahc wonders what the ID of the transformed Gokémon is if he only uses it once on a Gokémon of ID $x$. He wants you to write a program to predict it. One thing to notice is that Grahc has so many Gokémon, so he may ask you for more than one ID in one case.

That is, given a monotonic incremental function $f:\mathbb{N}^*\mapsto\mathbb{N}^*$ satisfying $f(f(x))=3x$. Now find $f(x_{i})$ for given $x_i$.

Format

Input

The first line of each input case contains an integer $T\,(1\leq T\leq 10)$ that represents how many IDs he wants you to predict.

The following $T$ lines contain one integer $x_i(1\leq x_i\leq 10^{18})$ each, representing the ID of the $i$-th Gokémon before transformation.

It is guaranteed that the sum of all $x_i$ does not exceed $3^{38}$.

Output

For every ID $x_i$, print the ID of the $i$-th Gokémon after transformation $f(x_i)$.

Samples

1
4

7

2
1
2

2
3