Загадка Прайма
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рик засек следы Рика Прайма, но, когда он прибыл на место, тот уже успел скрыться, оставив за собой только странную последовательность. Наш Рик C-137 уверен, что Рик Прайм оставил там подсказку к тому, где его искать, и теперь старается расшифровать всю скрытую в последовательности информацию.

Последовательность начинается как $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$8$$$, $$$12$$$, $$$5$$$, $$$10$$$, $$$15$$$, и так далее. Рик почти сразу догадался, как она образуется:

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

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

Входные данные

Первая строка содержит одно целое число $$$t$$$ — количество интересующих Рика элементов последовательности ($$$1 \le t \le 1000$$$).

В $$$i$$$-й из следующих $$$t$$$ строк дано единственное целое число $$$n_i$$$ — позиция $$$i$$$-го интересующего Рика элемента последовательности ($$$1 \le n \le 10^{15}$$$).

Выходные данные

Для каждого $$$n_i$$$ выведите $$$n_i$$$-е число этой загадочной последовательности.

Пример

Входные данные
9
1
2
3
4
5
6
7
8
9
Выходные данные
1
2
3
4
8
12
5
10
15