#P1249C2. Good Numbers (hard version)
Good Numbers (hard version)
No submission language available for this problem.
Description
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.
Input
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}$).
Output
For each query, print such smallest integer $m$ (where $n \le m$) that $m$ is a good number.
Samples
8
1
2
6
13
14
3620
10000
1000000000000000000
1
3
9
13
27
6561
19683
1350851717672992089