Рик засек следы Рика Прайма, но, когда он прибыл на место, тот уже успел скрыться, оставив за собой только странную последовательность. Наш Рик C-137 уверен, что Рик Прайм оставил там подсказку к тому, где его искать, и теперь старается расшифровать всю скрытую в последовательности информацию.
Последовательность начинается как $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$8$$$, $$$12$$$, $$$5$$$, $$$10$$$, $$$15$$$, и так далее. Рик почти сразу догадался, как она образуется:
Чтобы отследить Рика Прайма, необходимо научиться быстро узнавать $$$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