CF1249C2 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$。每个输出占一行