Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C2. Good Numbers (hard version)

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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.

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.

Example

Input

8 1 2 6 13 14 3620 10000 1000000000000000000

Output

1 3 9 13 27 6561 19683 1350851717672992089

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/29/2020 22:10:02 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|