CF1249C2.Good Numbers (hard version)

The only difference between easy and hard versions is the maximum value of $n$.

You are given a positive integer number $n$. You really love good numbers so you want to find the smallest good number greater than or equal to $n$.

The positive integer is called good if it can be represented as a sum of distinct powers of $3$ (i.e. no duplicates of powers of $3$ are allowed).

For example:

• $30$ is a good number: $30 = 3^3 + 3^1$,
• $1$ is a good number: $1 = 3^0$,
• $12$ is a good number: $12 = 3^2 + 3^1$,
• but $2$ is not a good number: you can't represent it as a sum of distinct powers of $3$ ($2 = 3^0 + 3^0$),
• $19$ is not a good number: you can't represent it as a sum of distinct powers of $3$ (for example, the representations $19 = 3^2 + 3^2 + 3^0 = 3^2 + 3^1 + 3^1 + 3^1 + 3^0$ are invalid),
• $20$ is also not a good number: you can't represent it as a sum of distinct powers of $3$ (for example, the representation $20 = 3^2 + 3^2 + 3^0 + 3^0$ is invalid).

Note, that there exist other representations of $19$ and $20$ as sums of powers of $3$ but none of them consists of distinct powers of $3$.

For the given positive integer $n$ find such smallest $m$ ($n \le m$) that $m$ is a good number.

You have to answer $q$ independent queries.

简单版本与困难版本的唯一区别在于 $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$ 的幂之和的方式，但其中均不满足所有幂互不相同这一条件。

对于给定的正整数 $n$，请找出满足 $n \le m$ 的最小的 $m$，使得 $m$ 是一个好数。

你需要回答 $q$ 个相互独立的查询。

The first line of the input contains one integer $q$ ($1 \le q \le 500$) — the number of queries. Then $q$ queries follow.

The only line of the query contains one integer $n$ ($1 \le n \le 10^{18}$).

输入的第一行包含一个整数 $q$（$1 \le q \le 500$），表示查询次数。随后是 $q$ 次查询。

每次查询仅包含一行，其中有一个整数 $n$（$1 \le n \le 10^{18}$）。

For each query, print such smallest integer $m$ (where $n \le m$) that $m$ is a good number.

对于每个查询，输出满足条件的最小整数 $m$（其中 $n \le m$），使得 $m$ 是一个“好数”。