Задача . C2. Хорошие числа (сложная версия)

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