F. Sequence Riddle
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A vicious criminal that a famous detective was following for a year disappeared, leaving behind only a strange sequence. Our detective is convinced that an insane criminal left a clue there about where to find him, and now he is trying to decipher all the hidden information in the sequence.

The sequence starts as $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$8$$$, $$$12$$$, $$$5$$$, $$$10$$$, $$$15$$$, and so on. The detective almost immediately figured out how it is formed:

  1. Initially, an empty sequence is taken;
  2. Then the smallest natural number that has not appeared in the sequence is chosen (for convenience, let's call it $$$x$$$);
  3. The numbers $$$x$$$, $$$2 \cdot x$$$, and $$$3 \cdot x$$$ are written one after another at the end of the sequence;
  4. The process returns to step 2.

To track the criminal, it is necessary to learn how to quickly find the $$$n$$$-th number of this sequence. Help the detective with this task!

Input

The first line contains a single integer $$$t$$$ — the number of elements of the sequence that the detective is interested in ($$$1 \le t \le 1000$$$).

In the $$$i$$$-th of the following $$$t$$$ lines, there is a single integer $$$n_i$$$ — the position of the $$$i$$$-th element of the sequence that you need to find ($$$1 \le n \le 10^{15}$$$).

Output

For each $$$n_i$$$, output the $$$n_i$$$-th number of this mysterious sequence.

Example
Input
9
1
2
3
4
5
6
7
8
9
Output
1
2
3
4
8
12
5
10
15