Странная последовательность
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Как-то раз Герман нашёл в интернете странную последовательность: $$$1, 2, 3, 4, 8, 12, 5, 10, 15, ...$$$ Герман почти сразу догадался, как она образуется:

1) Изначально у нас есть пустая последовательность;

2) выбирается наименьшее натуральное число, ни разу не встречающееся в последовательности (для удобства назоём его $$$x$$$);

3) в конец последовательности одно за другим записываются числа $$$x$$$, $$$2 \cdot x$$$ и $$$3 \cdot x$$$;

4) возвращаемся к шагу 2.

Теперь Герман хочет научиться быстро узнавать $$$n$$$-е число этой последовательности. Помогите ему!

Input

Первая строка теста содержит одно целое число $$$t$$$ $$$(1 \le t \le 10^3)$$$ — количество наборов входных данных. Затем следуют $$$t$$$ наборов входных данных.

Единственная строка набора входных данных содержит единственное число $$$n$$$ $$$(1 \le n \le 10^{15})$$$.

Output

Для каждого набора входных данных, выведите $$$n$$$-е число странной последовательности.

Example

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