C1. Хитрый продавец (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Простая версия отличается от сложной тем, что в ней требуется определить минимальную стоимость при наименьшем количестве сделок, а в сложной требуется определить минимальную стоимость при ограниченном количестве сделок.

После того как хитрый продавец продал три арбуза вместо одного, он решил увеличить свою прибыль — а именно, закупил ещё больше арбузов. Теперь он может продавать одновременно $$$3^x$$$ арбузов за $$$3^{x+1} + x \cdot 3^{x-1}$$$ монет, где $$$x$$$ — целое неотрицательное число. Одна такая продажа называется сделкой.

К нему пришёл расчётливый покупатель, но у него критически мало времени. В связи с этим он хочет купить ровно $$$n$$$ арбузов, совершив наименьшее возможное количество сделок.

Покупатель очень торопится и поэтому обратился к вам с просьбой определить наименьшую стоимость $$$n$$$ арбузов с учётом того, что он совершит наименьшее возможное количество сделок.

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

В первой строке дано целое число $$$t$$$ $$$(1 \le t \le 10^4)$$$ — количество наборов входных данных. Далее следует описание каждого набора.

В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ $$$(1 \le n \le 10^9)$$$ — сколько арбузов нужно купить.

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

Для каждого набора входных данных выведите одно целое число — минимальную стоимость арбузов.

Пример
Входные данные
7
1
3
8
2
10
20
260010000
Выходные данные
3
10
26
6
36
72
2250964728
Примечание

Заметим, что нет смысла покупать арбузов больше, чем нужно, так что не будем рассматривать сделки, где арбузов больше, чем надо.

Рассмотрим стоимости первых двух вариантов сделок:

Сделка А: $$$1$$$ арбуз — $$$3$$$ монеты.

Сделка Б: $$$3$$$ арбуза — $$$10$$$ монет.

В первом примере можно единственным образом купить $$$1$$$ арбуз, воспользовавшись сделкой А, — поэтому ответ $$$3$$$.

Во втором примере можно купить $$$3$$$ арбуза одной сделкой Б за $$$10$$$ монет.

В третьем примере можно совершить $$$2$$$ сделки А и $$$2$$$ сделки Б, что суммарно будет стоить $$$26$$$ монет. Если мы сделаем $$$3$$$ сделки, то можем получить $$$3$$$, $$$5$$$, $$$7$$$ или $$$9$$$ арбузов. Если сделаем меньше $$$3$$$ сделок, то получим не более $$$6$$$ арбузов, а значит меньше чем за $$$4$$$ сделки купить $$$8$$$ арбузов невозможно.