Good Numbers (hard version)

题意翻译

简单难度与困难难度的唯一差别是n的取值范围 现在给出一个定义：Good Number（下文以好数代替），好数是指可以变成3的**不同**次幂的加和的数 例如： $30$ 是好数 $30=3^3+3^1$ $1$ 是好数 $1=3^0$ $12$ 是好数 $12=3^2+3^1$ $2$ 不是好数，因为$2=3^0+3^0$，不符合不同次幂的条件 $19$ 不是好数，例如$19=3^2+3^2+3^0=3^2+3^1+3^1+3^1+3^0$，不符合不同次幂的条件 $20$不是好数，同理不符合不同次幂的条件，无法把$20$分为$3$的不同次幂的加和 现在给你一些正整数$n$，对于每个$n$请你给出一个最小的$m$满足：①$m$是好数 ②$n≤m$ ### 输入格式 输入第一行为一个正整数$q(1≤q≤500)$，表示有$q$个样例 然后有$q$行，每行一个正整数$n(1≤n≤10^{18})$ ### 输出格式 对于每个$n$，输出最小的$m$满足：①$m$是好数 ②$n≤m$。每个输出占一行

题目描述

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.

输入输出样例

输入样例 #1

8
1
2
6
13
14
3620
10000
1000000000000000000

输出样例 #1

1
3
9
13
27
6561
19683
1350851717672992089