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.

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}$ ).

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