Единственное отличие между простой и сложной версиями — максимальное значение $$$n$$$.

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

Положительное число называется хорошим, если оно может быть представлено в виде суммы различных степеней $$$3$$$ (т.е. повторения степеней $$$3$$$ запрещены).

Например:

• $$$30$$$ — хорошее число: $$$30 = 3^3 + 3^1$$$,
• $$$1$$$ — хорошее число: $$$1 = 3^0$$$,
• $$$12$$$ — хорошее число: $$$12 = 3^2 + 3^1$$$,
• но $$$2$$$ не является хорошим числом: вы не можете представить его в виде суммы различных степеней $$$3$$$ ($$$2 = 3^0 + 3^0$$$),
• $$$19$$$ не является хорошим числом: вы не можете представить его в виде суммы различных степеней $$$3$$$ (например, представления $$$19 = 3^2 + 3^2 + 3^0 = 3^2 + 3^1 + 3^1 + 3^1 + 3^0$$$ не являются корректными),
• $$$20$$$ тоже не является хорошим числом: вы не можете представить его в виде суммы различных степеней $$$3$$$ (например, представление $$$20 = 3^2 + 3^2 + 3^0 + 3^0$$$ не является корректным).

Обратите внимание, что существуют и другие представления $$$19$$$ и $$$20$$$ в качестве сумм степеней $$$3$$$, но ни одно из них не состоит из различных степеней $$$3$$$.

Для заданного положительного числа $$$n$$$ найдите наименьшее $$$m$$$ ($$$n \le m$$$) такое, что $$$m$$$ — хорошее число.

Вам необходимо ответить на $$$q$$$ независимых запросов.