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.


-----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

Difficulty: introductory

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())

	bits = ['1']
	while int(''.join(bits), 3) < n:
		bits.append('1')
	
	
	for i in range(len(bits)):
		bits[i] = '0'
		if int(''.join(bits), 3) < n:
			bits[i] = '1'
	
	print(int(''.join(bits), 3))


q = int(input())
for i in range(q):
    n = int(input())
    prod = 1
    prods = [1]
    sum1 = 0
    a = []
    while prod < n:
        sum1 += prod
        a.append(1)
        prod *= 3
        prods.append(prod)
    if sum1 < n:
        print(prod)
    else:
        for i in range(len(prods) - 1, -1, -1):
            if sum1 - prods[i] >= n:
                sum1 -= prods[i]
        print(sum1)

from math import log
for _ in range(int(input())):
    n = int(input())
    s = []
    x = int(log(n, 3))
    while x >= 0:
        if n >= 2 * 3 ** x:
            n -= 2 * 3 ** x
            s.append(2)
        elif n >= 3 ** x:
            n -= 3 ** x
            s.append(1)
        else:
            s.append(0)
        x -= 1
    s = s[::-1]
    l2 = 2229222
    for i in range(len(s)):
        if s[i] == 2:
            l2 = i
    if l2 != 2229222:
        f = 1
        for i in range(len(s)):
            if i <= l2:
                s[i] = 0
            else:
                if s[i] == 0:
                    s[i] = 1
                    f = 0
                    break
                else:
                    s[i] = 0
        if f:
            s.append(1)
    ans = 0
    for i in range(len(s)):
        ans += 3 ** i * int(s[i])
    print(ans)

def base3(n):
    # 17 -> [2, 2, 1] (reversedd)
    array = []
    while n > 0:
        array.append(n % 3)
        n //= 3
    return array
def good(n):
    return 2 not in base3(n)
def convert(array):
    return sum(array[i] * 3 ** i for i in range(len(array)))

for _ in range(int(input())):
    n = base3(int(input()))
    i = 0
    # print(n)
    # [1, 1, 2, 1, 2, 1, 0, 0, 1, 2, 0, 2, 1] ->
    # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1]
    for i in range(len(n) - 1, -1, -1):
        if n[i] == 2:
            for j in range(i - 1, -1, -1):
                n[j] = 0
            break
    i = 0
    while i < len(n):
        # Carry
        if n[i] > 2:
            if i < len(n) - 1:
                n[i + 1] += n[i] // 3
            else:
                n.append(n[i] // 3)
            n[i] %= 3
        # Is it 2
        if n[i] == 2:
            if i < len(n) - 1:
                n[i + 1] += 1
            else:
                n.append(1)
            n[i] = 0
        i += 1
    print(convert(n))
    # print()


# coding: utf-8
# Your code here!
def tobase3(n):
    a = []
    while(n>0):
        a.append(n%3)
        n//=3
    a.reverse()
    return a
    
def todec(a):
    sum=0;
    for i in range(len(a)):
        sum*=3
        sum+=a[i]
    return sum
    
    
t  = int(input())
for _ in range(t):
    n = int(input())
    a = tobase3(n)
    j=0
    flag = False
    for i in range(len(a)):
        if(a[i]==2):
            flag = True
            j=i
            while(j>=0 and a[j]!=0):
                j-=1
            break
    if(j<0 and flag):
        print(3**len(a))
    elif(flag):
        print(todec(a[:j]+[1]+[0]*(len(a)-j-1)))
    else:
        print(n)

arr = [3**i for i in range(40)]
s = sum(arr)
t = int(input())
for _ in range(t):
    n = int(input())
    m = s
    for i in arr[::-1]:
        if m - i >= n:
            m -= i
    print(m)


q = int(input())
for fwewfe in range(q):
	n = int(input())
	sk = 1
	su = 0
	while su < n:
		su += sk
		sk *= 3
	while su >= n and sk > 0:
		if su - sk >= n:
			su -= sk
		sk //= 3
	print(su)

import sys
input = sys.stdin.readline

q=int(input())

def calc(n):
    for i in range(40):
        if n<=3**i:
            break
        
    if n==3**i:
        return n
    
    elif n>(3**i-1)//2:
        return 3**i
    
    else:
        n-=3**(i-1)
        return 3**(i-1)+calc(n)

    

for testcases in range(q):
    n=int(input())
    print(calc(n))

    


import bisect


t = int(input())

tmp_ans = [0]*40
for i in range(40):
    tmp_ans[i] = 3**i
ruiseki = [0]*41
for i in range(40):
    ruiseki[i+1] = ruiseki[i] + tmp_ans[i]

for _ in range(t):
    n = int(input())
    ind = bisect.bisect_left(ruiseki, n)
    ans = ruiseki[ind]
    
    for i in range(ind)[::-1]:
        if ans - tmp_ans[i] >= n:
            ans -= tmp_ans[i]
    print(ans)

def main():
    q = int(input())
    thirds = [1]
    while thirds[-1] < 1e19:
        thirds.append(thirds[-1] * 3)
    for t in range(q):
        a = int(input())
        deg = 0
        subans = 0
        while subans < a:
            subans += thirds[deg]
            deg += 1
        while deg != -1:
            if subans - thirds[deg] >= a:
                subans -= thirds[deg]
            deg -= 1
        print(subans)


main()



q = int(input())
N = [int(input()) for i in range(q)]
t = [3**i for i in range(10)]

def d(x):
    ans = 0
    m = 1
    while x > 0:
        if x % 2 == 1:
            ans += m
        m *= 3
        x //= 2
    return(ans)

# print(d(2))


for i in range(q):
    n = N[i]
    m = 0
    t = 0
    l = 0
    r = 2**50
    mid = (l+r)//2
    while r - l > 1:
        
        m = d(mid)
        if m >= n:
            r = mid
        else:
            l = mid
        mid=(l+r)//2

    print(d(l+1))





t = int(input(''))

def ternary (n):
    if n == 0:
        return '0'
    nums = []
    while n:
        n, r = divmod(n, 3)
        nums.append(str(r))
    return ''.join(reversed(nums))

for _ in range(t):
    n = int(input(''))
    b = ternary(n)
    l = len(b)
    #print(b)
    ind = -1
    ans = ''
    for i in range(l):
        if(b[i] == '2'):
            ans = '0'*(l-i)
            ind = i
            break
    if(ind == 0):
        ans = '1'+ans
    elif(ind == -1):
        ans = b
    else:
        ind1 = -1
        for i in range(ind-1,-1,-1):
            if(b[i] == '1'):
                ans = '0'+ans
            else:
                ans = '1'+ans
                ind1 = i
                break
        if(ind1 == -1):
            ans = '1'+ans
        else:
            ans = b[0:ind1]+ans
    
    print(int(ans,3))
        
    


q = int(input())
for i in range(q):
    n = int(input())
    s = 0
    i = -1
    while s < n:
        i += 1
        s += 3 ** i
    if s == n:
        print(s)
    else:
        for j in range(i, -1, -1):
            if s - 3 ** j >= n:
                s -= 3 ** j
        print(s)

"""
NTC here
"""
from sys import stdin, setrecursionlimit
setrecursionlimit(10**7)


def iin(): return int(stdin.readline())
 
 
def lin(): return list(map(int, stdin.readline().split()))


# range = xrange
# input = raw_input

MAX_INT=99999999

def p3(a):
    ans=[]
    while a:
        ans.append(a%3)
        a//=3
    return ans
def main():
    t=iin()
    while t:
        t-=1
        n=iin()
        pw=p3(n)+[0,0]
        # print(pw)
        l=len(pw)
        ch=1
        for i in range(l-3,-1,-1):
            if pw[i]>1 :
                if ch:
                    pw[i]=0
                    pw[i+1]+=1
                    ch=0
                else:
                    pw[i]=0
            if ch==0:
                pw[i]=0
        for i in range(l-1):
            if pw[i]>1:pw[i]=0;pw[i+1]+=1
        ans=0
        pw=pw[::-1]
        for i in pw:
            ans=ans*3+i
        print(ans)



        







main()
# try:
#     main()
# except Exception as e: print(e)


tc = int(input())

def ternary (n):
    if n == 0:
        return '0'
    nums = []
    while n:
        n, r = divmod(n, 3)
        nums.append(str(r))
    return list(reversed(nums))

# print("here --> " + ternary(6561))
# print("here --> " + ternary(3620))
# print(ternary(4))
while tc > 0:
	tc -= 1
	n = int(input());
	rep = ['0'] + ternary(n)
	idx = -1
	for i in range(len(rep)):
		if rep[i] == '2':
			idx = i - 1;

			while rep[idx] != '0':
				idx -= 1
			rep[idx] = '1'
			for j in range(idx + 1 , len(rep)):
				rep[j] = '0'
	
	# print(rep)
	ans = 0
	for j in rep:
		x = ord(j) - ord('0')
		ans = ans * 3 + x
	print(ans)


#started 20 minutes late !

# print(len(str(3**36)))
arr=[]
for i in range(40):
    arr.append(3**i)
# print(arr)

n=int(input())
for i in range(n):
    sb=[0]*40
    a=int(input())
    x=a
    xx=a
    for j in range(39,-1,-1):
        if(a-arr[j]>=0):
            a-=arr[j]
            sb[j]=1
    # print(x-a,1)
    x=x-a
    # print(sb)
    if(a==0):
        print(x)
        continue
    for j in range(40):
        if(sb[j]==0):
            x=x+3**j
        # if(x>xx):
            break
        else:
            x=x-3**j
    print(x)
# print(3**8)


import sys
def I():
    return sys.stdin.readline().rstrip()

N = 39
p = [ 3 ** i for i in range( N ) ]

q = int( I() )
for _ in range( q ):
    n = int( I() )
    a = [ 0 ] * N
    for i in range( N - 1, -1, -1 ):
        d = n // p[ i ]
        n -= d * p[ i ]
        if d == 2:
            j = i + 1
            while a[ j ]:
                a[ j ] = 0
                j += 1
            a[ j ] = 1
            break
        a[ i ] = d
    n = 0
    for i in range( N ):
        if a[ i ]:
            n += p[ i ]
    print( n )


# -*- coding: utf-8 -*-
# @Author: apikdech
# @Date:   22:07:23 22-10-2019
# @Last Modified by:   apikdech
# @Last Modified time: 22:15:02 22-10-2019
def to_string(n):
	res = ''
	while(n):
		res = str(n%3) + res
		n //= 3
	res = list(res)
	return res

def to_int(s):
	res = 0
	for i in range(len(s)):
		res *= 3
		res += int(s[i])
	return res

q = int(input())
for _ in range(q):
	n = int(input())
	s = to_string(n)
	good = False
	while(not good):
		cnt = 0
		idx = 10000
		for i in range(len(s)):
			if (s[i] == '2'):
				cnt += 1
				idx = min(idx, i)
		if (cnt == 0) : good = True
		if (not good):
			for i in range(idx+1, len(s)):
				s[i] = '0'
			n = to_int(s)
			n += 3**(len(s) - idx - 1)
			s = to_string(n)
	print(n)

# for _ in range(int(input())):
#     n=int(input())
# print((3**38)//10**18)    
a=[3**i for i in range(39)]
for _ in range(int(input())):
    n=int(input())
    ans=0
    for i in range(38,-1,-1):
        if n-a[i]>=0:
            n-=a[i]
            ans+=a[i]
        elif n-a[i]<0 and  (3**i - 1)//2 <n:
            n-=a[i]
            ans+=a[i]
    print(ans)        
        
        



from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 1000010
MOD = 10**9+7
spf = [i for i in range(MAXN)]
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i*i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]

def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))

def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))

def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD

    return (num*(pow(den,MOD-2,MOD)))%MOD

def flush():
    return sys.stdout.flush()

'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''

def ternary (n):
    if n == 0:
        return '0'
    nums = []
    while n:
        n, r = divmod(n, 3)
        nums.append(str(r))
    return ''.join(reversed(nums))


for _ in range(int(input())):
    n = int(input())
    x = ternary(n)
    if '2' not in x:
        print(n)
    else:
        car = 0
        x = x[::-1]
        ans = [i for i in x]
        for i in range(len(x)):
            if x[i]=='2':
                for j in range(i,-1,-1):
                    ans[j] = '0'
                car = 1
            elif x[i]=='1':
                if car == 1:
                    for j in range(i,-1,-1):
                        ans[j] = '0'
            else:
                if car==1:
                    ans[i] = '1'
                    car = 0
        if car==1:
            ans.append('1')
        ans = ''.join(ans[::-1])
        print(int(ans,3))



T = int(input())
while T>0:
    T-=1
    n=int(input())
    ss = n
    a=[]
    while n>0:
        a.append(n%3)
        n=n//3
    fd = -1
    a.append(0)
    p = len(a)
    for i in range(p-1,-1,-1):
        if a[i]==2:
            fd = i
            break
    if fd ==-1:
        print(ss)
    else:
        for i in range(fd,p):
            if a[i]==0:
                a[i]=1
                for j in range(0,i):
                    a[j]=0
                break
        ans,k=0,1
        for i in range(0,p):
            ans += a[i]*k
            k*=3
        print(ans)


q = int(input())


def dec_to_base(N, base):
    if not hasattr(dec_to_base, 'table'):
        dec_to_base.table = '0123456789ABCDEF'
    x, y = divmod(N, base)
    return dec_to_base(x, base) + dec_to_base.table[y] if x else dec_to_base.table[y]


for i in range(q):
    n = int(input())
    s = list(str(dec_to_base(n, 3)))
    balance = n
    for i in range(len(s) - 1, -1, -1):
        if s[i] == "2":
            balance -= 3 ** (len(s) - i - 1)
            s[i] = "1"
    for i in range(len(s) - 1, -1, -1):
        if balance >= n:
            break
        if s[i] == "0" and balance < n:
            s[i] = "1"
            balance += 3 ** (len(s) - i - 1)
    while balance < n:
        balance *= 3
        s.append("0")
        if balance < n:
            s[-1] = "1"
            balance += 1
        else:
            break
    for i in range(len(s)):
        if balance - 3 ** (len(s) - i - 1) >= n:
            balance -= 3 ** (len(s) - i - 1)
            s[i] = '0'
    print(int(''.join(s), 3))


q = int(input())
out = []
for i in range(q):
    n = int(input())
    mm = 1
    sts = []
    while mm < n:
        sts.append(mm)
        mm *= 3
    sts.append(mm)
    m = sum(sts)
    for i in range(len(sts) - 1, -1, -1):
        if m - sts[i] < n:
            continue
        else:
            m -= sts[i]
    out.append(str(m))
print('\n'.join(out))

for _ in range(int(input())):
    n = int(input())
    l = []
    j = -1
    while (n):
        temp1 = n % 3
        n = n // 3
        if (temp1 == 2):
            temp1 = 0
            j = len(l)
        l.append(temp1)
    l.append(0)
    # print(l, j)
    if (j != -1):
        for i in range(j):
            l[i] = 0
        l[j + 1] += 1
        while (l[j + 1] == 2):
            j = j + 1
            l[j] = 0
            l[j + 1] += 1
    # print(l)
    s = ''
    for i in l[::-1]:
        s += str(i)
    print(int(s, 3))