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

Единственное отличие между простой и сложной версиями — максимальное значение $$$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$$$ независимых запросов.

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

Первая строка входных данных содержит одно целое число $$$q$$$ ($$$1 \le q \le 500$$$) — количество запросов. Затем следуют $$$q$$$ запросов.

Единственная строка запроса содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^4$$$).

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

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

Пример
Входные данные
7
1
2
6
13
14
3620
10000
Выходные данные
1
3
9
13
27
6561
19683