Set Definition

The set $S$ is defined by the following rules.

1. $1$ is an element of $S$.
2. If $X$ is an element of $S$, then $2X+1$ and $3X+1$ are also elements of $S$.
3. A number that these two rules do not produce is not an element of $S$.

$S$ is a set, so a value reachable in more than one way still counts as a single element.

List the elements of $S$ in increasing order and find the $N$-th value.

The first line contains the number of test cases $T$ ($1 \le T \le 200$). Each of the next $T$ lines contains one integer $N$ ($1 \le N \le 10^7$).

For each test case, print the $N$-th smallest element of $S$ on its own line.