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: MEDIUM
Tags: Complete search

Sorting

Mathematics

Greedy algorithms
Skill types: Complete search

Sorting

Greedy algorithms

Starter code:

Solutions:
for q in range(int(input())):
	n = int(input())
	a = n
	base3 = []
	while n != 0:
		base3.append(n % 3)
		n = n // 3
	base3.reverse()
	if 2 in base3:
		for i in range(len(base3)):
			if base3[i] == 2:
				if 0 in base3[1:i]:
					p = len(base3[1:i]) - base3[1:i][::-1].index(0)
					base3[p] = 1
					n = 0
					for t in range(p + 1):
						n += base3[t] * 3 ** (len(base3) - t - 1)
				else:
					base3[0] = 1
					n = 3 ** len(base3)
				break
		print(n)
	else:
		print(a)


a = [3 ** i for i in range(40)]
for _ in range(int(input())):
	n = int(input())
	x = sum(a)
	for i in a[::-1]:
		if x - i >= n:
			x -= i
	print(x)


import sys, math, bisect

def input():
	return sys.stdin.readline()[:-1]

def main():
	q = int(input())
	for _ in range(q):
		n = int(input())
		ans = 0
		t = 0
		m = 0
		while n > m:
			m += 3 ** t
			t += 1
		for k in range(t + 1, -1, -1):
			if m - 3 ** k >= n:
				m -= 3 ** k
		print(m)
main()


for _ in range(int(input())):
	n = int(input())
	ans = n
	t = []
	while n:
		d = n % 3
		n //= 3
		t = [d] + t
	t = [0] + t
	if max(t) == 1:
		print(ans)
	else:
		i = 0
		while t[i] < 2:
			i += 1
		j = i - 1
		while t[j] == 1:
			j -= 1
		t[j] = 1
		k = 0
		bs = 1
		for c in range(len(t) - 1, -1, -1):
			if c <= j:
				k += bs * t[c]
			bs *= 3
		print(k)


t = int(input(''))
num = []
for i in range(t):
	num.append(int(input('')))
for i in num:
	digits = []
	while i:
		digits.append(i % 3)
		i = int(i // 3)
	digits.append(0)
	lst = -1
	for j in range(len(digits)):
		if digits[j] == 2:
			lst = j
	if lst != -1:
		while digits[lst]:
			lst += 1
		for j in range(lst):
			digits[j] = 0
		digits[lst] = 1
	ans = 0
	m = 1
	for j in range(len(digits)):
		ans += digits[j] * m
		m *= 3
	print(ans)


def get_coefficients(n):
	coefficients = []
	while n >= 1:
		reminder = n % 3
		n = n // 3
		coefficients.append(reminder)
	return coefficients

def check_ranks(n, coefficients):
	zero_rank = -1
	coefficients.reverse()
	try:
		two_rank = coefficients.index(2)
		try:
			temp = coefficients[:two_rank].copy()
			temp.reverse()
			zero_rank = temp.index(0, 0, two_rank) + 1
			coefficients[two_rank - zero_rank] = 1
			zero_rank = two_rank - zero_rank
		except ValueError:
			zero_rank = -1
	except ValueError:
		two_rank = -1
	return (two_rank, zero_rank)
q = int(input())
for _ in range(q):
	n = int(input())
	coefficients = get_coefficients(n)
	(two_rank, zero_rank) = check_ranks(n, coefficients)
	if two_rank == -1:
		print(n)
	elif zero_rank == -1:
		s = 3 ** len(coefficients)
		print(s)
	else:
		s = 0
		for i in range(zero_rank + 1):
			s += 3 ** (len(coefficients) - 1 - i) * coefficients[i]
		print(s)


def intlog(num, base):
	n = num
	res = 0
	while n >= base:
		n //= base
		res += 1
	return res

def ceillog(num, base):
	n = num
	res = 0
	while n:
		n //= base
		res += 1
	return res
t = int(input())
while t:
	t -= 1
	n = int(input())
	maxx = ceillog(n, 3)
	p = []
	for i in range(maxx + 1):
		p.append(3 ** i)
	chk = sum(p[:-1])
	if chk < n:
		print(p[-1])
	else:
		while chk > n and p:
			if chk - p[-1] < n:
				p.pop()
			else:
				chk -= p[-1]
				p.pop()
		print(chk)


from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 7)

def iin():
	return int(stdin.readline())

def lin():
	return list(map(int, stdin.readline().split()))
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]
		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()


def task_3(n):
	division = n
	result = list()
	while division > 0:
		balance = division % 3
		division = division // 3
		result.append(balance)
	if 2 not in result:
		print(n)
	else:
		result.append(0)
		for (key, value) in enumerate(result):
			if value >= 2:
				result[0:key] = [0] * key
				result[key] = 0
				result[key + 1] += 1
		result_value = 0
		for (key, value) in enumerate(result):
			result_value += value * 3 ** key
		print(result_value)
q = int(input())
for q in range(q):
	(n,) = map(int, input().rstrip().split())
	task_3(n)


arr = []
for i in range(40):
	arr.append(3 ** i)
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
	x = x - a
	if a == 0:
		print(x)
		continue
	for j in range(40):
		if sb[j] == 0:
			x = x + 3 ** j
			break
		else:
			x = x - 3 ** j
	print(x)


import sys

def check(x):
	num = x
	ind = 0
	while True:
		org = x
		s = ''
		done = 1
		while x != 0:
			if x % 3 == 2:
				done = 0
			s = str(x % 3) + s
			x = x // 3
		if done == 1:
			if org == num:
				return num
			break
		c = 0
		for g in range(len(s) - 1, -1, -1):
			if s[g] == '2':
				ind = g
				break
			else:
				c += 1
		tmp = '1' + c * '0'
		x = int(tmp, 3) + org
	arr = []
	for f in range(len(s)):
		arr.append(s[f])
	for p in range(len(s) - 1, ind - 1, -1):
		if arr[p] == '1' and p != ind - 1 and (p != 0):
			arr[p] = '0'
	return int(''.join(arr), 3)
q = int(sys.stdin.readline())
ans_arr = []
for i in range(q):
	n = int(sys.stdin.readline())
	ans = check(n)
	ans_arr.append(str(ans))
print('\n'.join(ans_arr))


for q in range(int(input())):
	n = int(input())
	(pos2, val) = (-1, [])
	while n:
		i = n % 3
		val.append(i)
		if i == 2:
			pos2 = len(val) - 1
		n //= 3
	val.append(0)
	if pos2 != -1:
		pos0 = val[pos2:].index(0) + pos2
		val[pos0] = 1
		for i in range(pos0 - 1, -1, -1):
			val[i] = 0
	(ans, pw) = (0, 1)
	for i in val:
		ans += pw * i
		pw *= 3
	print(ans)


def to_base3(n):
	ost = n % 3
	if n == ost:
		return [str(ost)]
	return to_base3(n // 3) + [str(ost)]

def solution(n):
	base3 = to_base3(n)
	try:
		first2 = base3.index('2')
	except Exception:
		return int(''.join(base3), base=3)
	first0 = first2
	for i in range(first2):
		if base3[i] == '0':
			first0 = i
	if first0 == first2:
		return 3 ** len(base3)
	else:
		base3[first0] = '1'
		return int(''.join(base3[0:first0 + 1] + ['0'] * (len(base3) - 1 - first0)), base=3)
q = int(input())
for i in range(q):
	print(solution(int(input())))


for _ in range(int(input())):
	dp = [0 for i in range(40)]
	n = int(input())
	m = 0
	k = 1
	l = n
	while l >= 0:
		l -= k
		dp[m] = 1
		m += 1
		k = 3 ** m
	ans = 0
	for i in range(40):
		if dp[i]:
			ans += 3 ** i
	for i in range(39, -1, -1):
		k = 3 ** i
		if ans - k >= n:
			ans -= k
	print(ans)


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)


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(t,) = I()
for _ in range(t):
	(n,) = I()
	k = ''
	x = n
	while x:
		k += str(x % 3)
		x //= 3
	k = k[::-1]
	ix = 0
	if '2' not in k:
		print(n)
	else:
		p = k.find('2')
		if p == 0 or '0' not in k:
			k = '1' + '0' * len(k)
		else:
			f = n + 1
			l = p - 1
			while l > 0:
				if k[l] == '0':
					f = l
					break
				l -= 1
			if f < p:
				p = f
				k = k[:p] + '1' + '0' * (len(k) - p - 1)
			else:
				k = '1' + '0' * len(k)
		k = k[::-1]
		an = 0
		m = 1
		for i in k:
			an += int(i) * m
			m *= 3
		print(an)


t = int(input())
while t:
	n = int(input())
	orig = n
	l = []
	pos = -1
	while n > 0:
		l.append(n % 3)
		if l[-1] == 2:
			pos = len(l) - 1
		n //= 3
	if pos == -1:
		print(orig)
	else:
		i = 0
		for i in range(pos, len(l)):
			if l[i] == 0:
				l[i] = 1
				break
		if i == len(l) - 1:
			print(pow(3, len(l)))
		else:
			for j in range(0, i):
				l[j] = 0
			count = 0
			ans = 0
			for i in l:
				ans += i * pow(3, count)
				count += 1
			print(ans)
	t -= 1


def check(q):
	temp = []
	while q > 0:
		m = q % 3
		q = q - m
		q = q // 3
		temp.append(m)
	flag = -1
	for i in range(len(temp)):
		if temp[i] == 2:
			temp[i] = 0
			flag = i
	if flag == -1:
		return temp
	else:
		for i in range(flag + 1):
			temp[i] = 0
		for i in range(flag + 1, len(temp)):
			if temp[i] == 0:
				temp[i] = 1
				break
			else:
				temp[i] = 0
		else:
			temp.append(1)
		return temp
t = int(input())
for _ in range(t):
	q = int(input())
	s = check(q)
	num = 0
	for i in range(len(s)):
		num += s[i] * pow(3, i)
	print(int(num))


for _ in range(int(input())):
	a = [1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987, 22876792454961, 68630377364883, 205891132094649, 617673396283947, 1853020188851841, 5559060566555523, 16677181699666569, 50031545098999707, 150094635296999121, 450283905890997363, 1350851717672992089]
	n = int(input())
	if n in a:
		print(n)
	else:
		t = []
		for i in range(39):
			if a[i] > n:
				t.append(a.pop(i - 1))
				r = n - t[0]
				s = a[i - 1]
				break
		while r >= a[0] or r == 0:
			if r == 0:
				print(n)
				break
			for i in range(39):
				if a[i] > r:
					r = r - a[i - 1]
					t.append(a.pop(i - 1))
					break
		if r != 0:
			num = t[0] + a[0]
			while num < n:
				num += t.pop(1)
			print(min(num, s))


import sys
lines = sys.stdin.readlines()
q = int(lines[0])
for i in range(1, q + 1):
	n = int(lines[i])
	(i, max_i) = (0, 0)
	while 3 ** i <= n:
		if n % 3 ** (i + 1) >= 2 * 3 ** i:
			n += 3 ** i
			max_i = i
		i += 1
	n -= n % 3 ** max_i
	print(n)


def transfer_to_3(val):
	s = list()
	while val > 0:
		s.append(val % 3)
		val //= 3
	s = ''.join(map(str, s))
	return s[::-1]
n = int(input())
for i in range(0, n):
	x = int(input().strip())
	t = transfer_to_3(x)
	has_2 = False
	for (k, v) in enumerate(t):
		if v is '2':
			if k is 0:
				print(int('1' + '0' * len(t), 3))
			else:
				while k > 0:
					k -= 1
					if t[k] is '0':
						print(int(t[0:k] + '1' + '0' * (len(t) - 1 - k), 3))
						break
				else:
					print(int('1' + '0' * len(t), 3))
			break
	else:
		print(int(t, 3))


def ternary(x):
	ans = []
	while x > 0:
		ans.append(x % 3)
		x //= 3
	return ans
q = int(input())
for _ in range(q):
	n = int(input())
	ter = ternary(n)
	ter.append(0)
	if ter.count(2) == 0:
		print(n)
		continue
	idx = 0
	for i in range(len(ter)):
		if ter[i] == 2:
			idx = i
	idt = idx + 1
	for i in range(idx + 1, len(ter)):
		if ter[i] == 0:
			idt = i
			break
	for i in range(idt):
		ter[i] = 0
	ter[idt] = 1
	ter.reverse()
	ans = 0
	for i in ter:
		ans *= 3
		ans += i
	print(ans)


def po(a, b):
	if b < 0:
		return 0
	elif b == 0:
		return 1
	x = po(a, b // 2)
	if b % 2 != 0:
		return x * x * a
	return x * x
t = int(input())
for i in range(t):
	n = int(input())
	prev = 0
	while po(3, prev) <= n:
		prev = prev + 1
	ans1 = po(3, prev - 1)
	ans = 0
	n = n - ans1
	k = prev
	while n > 0:
		j = 0
		while po(3, j) <= n:
			j = j + 1
		if j == k:
			ans = ans + po(3, prev)
			break
		else:
			if k - j > 1:
				ans = ans + ans1
				prev = j
				ans1 = 0
			ans1 = ans1 + po(3, j - 1)
			k = j
			n = n - po(3, j - 1)
	if n == 0:
		ans = ans + ans1
	print(ans)


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


l = [1] + [0 for i in range(40)]
for i in range(1, 41):
	l[i] = l[i - 1] * 3
s = [l[0]] + [0 for i in range(40)]
for i in range(1, 41):
	s[i] = s[i - 1] + l[i]
for _ in range(int(input())):
	n = int(input())
	ans = 0
	while ans < n:
		for i in range(41):
			if s[i] + ans >= n:
				ans += l[i]
				break
	print(ans)


l = [0 for i in range(41)]
c = 1
for i in range(1, 41):
	l[i] = l[i - 1] + c
	c *= 3
for _ in range(int(input())):
	n = int(input())
	temp = 0
	for i in range(40, -1, -1):
		if l[i] < n:
			n -= l[i + 1] - l[i]
			temp += l[i + 1] - l[i]
	print(temp)


def linp():
	return list(map(int, input().split()))

def minp():
	return map(int, input().split())

def iinp():
	return int(input())

def test():
	return int(input())

def inp():
	return 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))

def solve():
	n = iinp()
	ter = ['0'] + list(ternary(n))
	z = 0
	flag = True
	i = 0
	for i in range(len(ter)):
		if ter[i] == '0':
			z = i
		elif ter[i] == '2':
			flag = False
			break
	if flag:
		print(int(''.join(ter), 3))
	else:
		ans = ter[:z] + ['1'] + ['0'] * (len(ter) - (z + 1))
		print(int(''.join(ans), 3))

def main():
	for _ in range(test()):
		solve()
main()


from sys import stdin
input = stdin.readline
from heapq import heapify, heappush, heappop, heappushpop
from collections import defaultdict as dd, deque as dq, Counter as C
from math import factorial as f, ceil, gcd, sqrt, log
from bisect import bisect_left as bl, bisect_right as br
from itertools import combinations as c, permutations as p
from math import factorial as f, ceil, gcd, sqrt, log
mp = lambda : map(int, input().split())
it = lambda : int(input())
ls = lambda : list(input().strip())
mt = lambda r: [list(mp()) for _ in range(r)]
lcm = lambda a, b: a * b // gcd(a, b)

def fibo_n(n):
	return ((1 + sqrt(5)) / 2) ** n / sqrt(5)
mod = 1000000007
n = 10 ** 18
v = [1]
while v[-1] <= n:
	v.append(v[-1] * 3)
v.append(v[-1] * 3)
for _ in range(it()):
	a = it()
	t = a
	mn = float('inf')
	flag = 0
	for j in range(len(v) - 1, -1, -1):
		if a >= v[j]:
			flag = max(flag, j)
			a -= v[j]
		else:
			mn = min(mn, v[j] - a)
	if a == 0:
		print(t)
	else:
		print(min(v[flag + 1], t + mn))


def Base_10_to_n(X, n):
	if X // n:
		return Base_10_to_n(X // n, n) + str(X % n)
	return str(X % n)
n = int(input())
for i in range(n):
	a = int(input())
	s = Base_10_to_n(a, 3)
	ng = False
	for c in s:
		if c == '2':
			ng = True
			break
	if not ng:
		print(a)
		continue
	ng = False
	for c in s:
		if c == '2':
			ng = True
			break
		if c == '0':
			break
	if ng:
		print(3 ** len(s))
		continue
	sz = len(s)
	for i in range(sz - 1, -1, -1):
		s = Base_10_to_n(a, 3)
		if s[i] == '2':
			bs = 3 ** (sz - 1 - i)
			a //= bs
			a *= bs
			a += bs
	ans = 3 ** (len(s) - 1)
	if ans >= a:
		print(ans)
	else:
		print(a)


def base3(n):
	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
	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):
		if n[i] > 2:
			if i < len(n) - 1:
				n[i + 1] += n[i] // 3
			else:
				n.append(n[i] // 3)
			n[i] %= 3
		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))


def solve():
	x = int(input())
	s = 0
	i = 0
	while s <= x:
		s += 3 ** i
		i += 1
	i -= 1
	while i >= 0:
		if s - 3 ** i >= x:
			s -= 3 ** i
		i -= 1
	return s
q = int(input())
print(*[solve() for i in range(q)], sep='\n')


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)


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)


a = []
for i in range(40):
	a.append(3 ** i)
a = a[::-1]
for nt in range(int(input())):
	n = int(input())
	s = sum(a)
	for i in a:
		if s - i >= n:
			s -= i
	print(s)


import sys
input = sys.stdin.readline
c = 1
arr = [1]
for i in range(1, 40):
	c = 3 * arr[i - 1]
	arr.append(c)
for _ in range(int(input())):
	y = int(input())
	sum = 0
	pos = 0
	for i in range(40):
		if sum < arr[i]:
			sum += arr[i]
			pos = i
		else:
			break
	while pos >= 0:
		if sum - arr[pos] >= y:
			sum -= arr[pos]
		pos -= 1
	print(sum)


import math
import sys
import collections
input = sys.stdin.readline

def getdict(n):
	d = {}
	if type(n) is list:
		for i in n:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
	else:
		for i in range(n):
			t = ii()
			if t in d:
				d[t] += 1
			else:
				d[t] = 1
	return d

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = prime[1] = False
	r = [p for p in range(n + 1) if prime[p]]
	return r

def pow(x, y, mod):
	r = 1
	x = x % mod
	while y > 0:
		if y & 1:
			r = r * x % mod
		y = y >> 1
		x = x * x % mod
	return r

def cdiv(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def to(n):
	r = []
	while n > 0:
		r.append(n % 3)
		n = n // 3
	r.append(0)
	return r

def fr(l):
	r = 0
	mul = 1
	for i in l:
		r += i * mul
		mul *= 3
	return r
t = ii()
for _ in range(t):
	n = ii()
	d = to(n)
	i = 0
	while i < len(d):
		if d[i] == 2:
			while d[i] != 0:
				i += 1
			d[i] = 1
			for j in range(i - 1, -1, -1):
				d[j] = 0
		i += 1
	print(fr(d))


from math import log
q = int(int(input()))
for i in range(q):
	n = int(input())
	t1 = int(log(n, 3))
	r = t1
	visited = [False] * (t1 + 1)
	min1 = float('inf')
	current = n
	while t1 >= 0:
		if current >= 3 ** t1:
			visited[t1] = True
			current = current - 3 ** t1
		else:
			min1 = 3 ** t1 - current
		t1 = t1 - 1
	if not current:
		print(n)
	elif min1 != float('inf'):
		print(n + min1)
	elif current > 0:
		print(3 ** (r + 1))


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import log, ceil

def f(m):
	x = 0
	j = 0
	while m:
		if m & 1:
			x += 3 ** j
		m >>= 1
		j += 1
	return x
for _ in range(int(input())):
	n = int(input())
	(l, r) = (1, 2 ** 42)
	ans = -1
	while l <= r:
		m = l + r >> 1
		if f(m) >= n:
			ans = f(m)
			r = m - 1
		else:
			l = m + 1
	print(ans)


q = int(input())
for i in range(0, q):
	n = int(input())
	l = []
	while n > 0:
		l.append(n % 3)
		n //= 3
	k = len(l)
	pos = 0
	for j in range(-1, -k - 1, -1):
		if l[j] == 2:
			pos = j
			break
	if pos != 0:
		for j in range(pos, -k - 1, -1):
			l[j] = 0
	if pos != 0:
		if pos == -1:
			l.append(1)
			k += 1
		else:
			while pos != -1:
				l[pos + 1] += 1
				if l[pos + 1] < 2:
					break
				l[pos + 1] = 0
				pos += 1
			else:
				l.append(1)
				k += 1
	res = 0
	for j in range(0, k):
		res += 3 ** j * l[j]
	print(res)


import os
import sys
from io import BytesIO, IOBase

def solve(n):
	a = []
	while n:
		a.append(n % 3)
		n //= 3
	a.append(0)
	a.append(0)
	a = a[::-1]
	for i in range(len(a)):
		if a[i] < 2:
			continue
		for j in range(i - 1):
			if a[i - j - 1] == 1:
				continue
			k = i - j - 1
			a[k] = 1
			a = a[:k + 1] + [0] * (len(a) - k - 1)
			break
		break
	n = 0
	for x in a:
		n = n * 3 + x
	print(n)

def main():
	for _ in range(int(input())):
		solve(int(input()))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math
for _ in range(int(input())):
	n = int(input())
	s = set()
	a = []
	su = 0
	n1 = n
	while su < n1:
		try:
			k = math.log(n, 3)
			k1 = int(k)
			k2 = int(math.ceil(k))
			cc = 3 ** k2
			if cc not in s:
				a.append(su + cc)
			lol = 3 ** k1
			if lol not in s:
				s.add(lol)
				su += lol
				if su >= n1:
					a.append(su)
					break
				n -= lol
			else:
				break
		except:
			break
	print(min(a))


def po(a, b):
	if b < 0:
		return 0
	elif b == 0:
		return 1
	x = po(a, b // 2)
	if b % 2 != 0:
		return x * x * a
	return x * x
t = int(input())
for i in range(t):
	n = int(input())
	l = []
	for j in range(40):
		l.append(0)
	while n != 0:
		j = 0
		while po(3, j) <= n:
			j = j + 1
		if l[j - 1] == 1:
			while l[j - 1] == 1:
				l[j - 1] = 0
				j = j + 1
			l[j - 1] = 1
			ans = 0
			j = 0
			while j < 40:
				if l[j] == 1:
					ans = ans + po(3, j)
				j = j + 1
			break
		else:
			l[j - 1] = 1
			n = n - po(3, j - 1)
	if n == 0:
		ans = 0
		j = 0
		while j < 40:
			if l[j] == 1:
				ans = ans + po(3, j)
			j = j + 1
	print(ans)


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 math
import sys
input = sys.stdin.readline
nu = 1
dic = {1: 0}
for i in range(1, 39):
	nu *= 3
	dic[nu] = i
for _ in range(int(input())):
	n = int(input())
	co = 0
	li = [60]
	flag = True
	while n:
		if n in dic:
			if li[-1] == dic[n]:
				flag = False
				break
			else:
				li.append(dic[n])
				co += 1
				break
		xx = int(math.log(n, 3))
		if li[-1] == xx:
			flag = False
			break
		else:
			li.append(xx)
			co += 1
			n -= 3 ** xx
	if flag:
		ans = 0
		for i in range(1, co + 1):
			ans += 3 ** li[i]
		print(ans)
	else:
		ans = 0
		for i in range(1, co + 1):
			if li[-i - 1] - li[-i] != 1:
				ans = 3 ** (li[-i] + 1)
				break
		for j in range(i + 1, co + 1):
			ans += 3 ** li[-j]
		print(ans)


foo = []
n = int(input())
for i in range(n):
	x = int(input())
	w = 3 ** 39
	q = x
	j = 40
	while q >= x:
		j -= 1
		q = 3 ** j
	q = 3 ** (j + 1)
	w = min(w, q)
	q = 3 ** j
	while q < x and j > 0:
		j -= 1
		q += 3 ** j
		if q >= x:
			w = min(w, q)
			q -= 3 ** j
	foo.append(w)
for i in foo:
	print(i)


def my_power(base, power):
	ans = 1
	while power > 0:
		if power % 2 != 0:
			ans *= base
		base = base * base
		power = power // 2
	return ans

def back_to_base_ten(ans_trans):
	observed_zero = False
	observe_one = False
	one_start = 0
	ans = 0
	for j in range(len(ans_trans)):
		if ans_trans[j] == 0 and (not observed_zero):
			observed_zero = True
			if j != 0:
				ans += my_power(3, one_start) * (my_power(3, j - one_start) - 1) // 2
			observe_one = False
		if ans_trans[j] == 1 and (not observe_one):
			observe_one = True
			one_start = j
			observed_zero = False
	if not observed_zero:
		ans += my_power(3, one_start) * (my_power(3, len(ans_trans) - one_start) - 1) // 2
	return ans

def find(c):
	d = c
	trans = []
	last_two_index = -1
	i = 0
	while d > 0:
		digit = d % 3
		if digit == 2:
			last_two_index = i
		i += 1
		trans.append(digit)
		d = d // 3
	ans_trans = []
	two_observed = False
	if last_two_index != -1:
		for i in range(len(trans)):
			done = False
			if not two_observed and i == last_two_index:
				two_observed = True
			if trans[i] == 0 and i > last_two_index and two_observed:
				two_observed = False
				ans_trans.append(1)
				done = True
			if not done:
				if i < last_two_index or two_observed:
					ans_trans.append(0)
				else:
					ans_trans.append(trans[i])
	else:
		ans_trans = trans
	if two_observed:
		ans_trans.append(1)
	ans = back_to_base_ten(ans_trans)
	return ans
ref = []
n = int(input())
for i in range(n):
	c = int(input())
	print(find(c))


for _ in range(int(input())):
	n = int(input())
	a = []
	b = [0]
	for i in range(50):
		a.append(3 ** i)
		b.append(b[-1] + a[-1])
		if b[-1] > n:
			break
	s = b[i + 1]
	a = a[::-1]
	for j in a:
		if s - j >= n:
			s -= j
	print(s)


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

def solve():
	n = int(input())
	s = list(ternary(n))
	s.append('0')
	changed = False
	for i in range(len(s) - 2, -1, -1):
		if changed:
			s[i] = '0'
			continue
		if s[i] == '2':
			s[i] = '0'
			j = i + 1
			while s[j] == '1':
				j += 1
				s[j - 1] = '0'
			s[j] = '1'
			changed = True
	ans = list(reversed(s))
	ans1 = ''.join(ans)
	print(int(ans1, 3))
for _ in range(int(input())):
	solve()


import math
for _ in range(int(input())):
	n = int(input())
	s1 = 0
	while n >= 3:
		a = int(math.log(n, 3)) + 1
		s = (pow(3, a) - 1) // 2
		if n > s:
			s1 += pow(3, a)
			break
		elif n == s:
			s1 += s
			break
		else:
			n -= pow(3, a - 1)
			s1 += pow(3, a - 1)
	if n == 2:
		s1 += 3
	if n == 1:
		s1 += 1
	print(s1)


def ter(n):
	l = []
	while True:
		l.append(n % 3)
		n = n // 3
		if n < 1:
			return l[::-1]
for _ in range(int(input())):
	n = int(input())
	l = ter(n)
	flag = False
	ind = -1
	for i in range(len(l) - 1, -1, -1):
		if l[i] > 1:
			flag = True
			l[i] = 0
			continue
		if flag and l[i] == 0:
			l[i] = 1
			ind = i
			flag = False
	if not flag:
		for i in range(len(l)):
			if ind != -1 and i > ind:
				l[i] = '0'
				continue
			l[i] = str(l[i])
		s = ''.join(l)
		print(int(s, 3))
	else:
		print(pow(3, len(l)))


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)
	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
	s = ''
	for i in l[::-1]:
		s += str(i)
	print(int(s, 3))


import sys
q = int(input())
for _ in range(q):
	n = int(input())
	l = []
	while n > 0:
		l.append(n % 3)
		n = n // 3
	ind = -1
	for i in range(len(l)):
		if l[i] == 2:
			ind = i
	if ind != -1:
		ind += 1
		while ind < len(l) and l[ind] == 1:
			ind += 1
		for j in range(ind):
			l[j] = 0
		if ind >= len(l):
			l.append(1)
		else:
			l[ind] = 1
	res = 0
	p3 = 1
	for i in range(len(l)):
		res += p3 if l[i] == 1 else 0
		p3 *= 3
	print(res)


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'
			elif car == 1:
				ans[i] = '1'
				car = 0
		if car == 1:
			ans.append('1')
		ans = ''.join(ans[::-1])
		print(int(ans, 3))


L = []
for i in range(0, 39):
	L.append(3 ** i)
q = int(input())
for _ in range(q):
	n = int(input())
	ans = 0
	while n > 0:
		ptr = 38
		for i in range(0, len(L)):
			if L[i] > n:
				ptr = i
				break
		if n > (L[ptr] - 1) / 2:
			ans += L[ptr]
			break
		else:
			n -= L[ptr - 1]
			ans += L[ptr - 1]
	print(ans)


def find_closest(num):
	sum_ = 0
	curr = 1
	degree = 0
	while sum_ < num:
		sum_ += curr
		curr *= 3
		degree += 1
	while degree != -1:
		if sum_ - curr >= num:
			sum_ -= curr
		curr = curr // 3
		degree -= 1
	return sum_
amount = int(input())
for i in range(amount):
	n = int(input())
	print(find_closest(n))


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)


def arr_inp():
	return [int(x) for x in input().split()]

def arr_sum():
	new_arr = [1]
	for i in range(1, 39):
		new_arr.append(new_arr[i - 1] + 3 ** i)
	return new_arr
from math import *
mem = arr_sum()
for i in range(int(input())):
	n = int(input())
	ix = ceil(log(n, 3))
	s = mem[ix]
	for j in range(ix, -1, -1):
		ex = s - 3 ** j
		if ex >= n:
			s -= 3 ** j
	print(s)


q = int(input())
for i in range(q):
	n = int(input())
	trinary = []
	while n > 0:
		trinary.append(n % 3)
		n //= 3
	trinary += [0]
	flag = False
	for j in range(len(trinary) - 1, -1, -1):
		if flag:
			trinary[j] = 0
		elif trinary[j] == 2:
			k = j
			while k < len(trinary) and trinary[k] == 2:
				trinary[k] = 0
				trinary[k + 1] += 1
				k += 1
			flag = True
	answ = 0
	for j in range(len(trinary)):
		if trinary[j] == 1:
			answ += pow(3, j)
	print(answ)


def r():
	return map(int, input().split())

def ternary(n):
	if n == 0:
		return '0'
	nums = []
	while n:
		(n, r) = divmod(n, 3)
		nums.append(str(r))
	return ''.join(reversed(nums))
t = int(input())
for _ in range(t):
	n = int(input())
	y = ternary(n)
	if '2' in y:
		val = '1' * len(y)
		if int(val, 3) < n:
			print(3 ** len(y))
		else:
			v = list(val)
			for i in range(1, len(val)):
				temp = list(v)
				temp[i] = '0'
				if int(''.join(temp), 3) >= n:
					v = list(temp)
			print(int(''.join(v), 3))
	else:
		print(n)


from math import log
li = []
for i in range(40):
	li.append(3 ** i)
for _ in range(int(input())):
	sum1 = sum(li)
	x = int(input())
	for i in li[::-1]:
		if sum1 - i >= x:
			sum1 -= i
	print(sum1)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()
for _ in range(inp()):
	n = inp()
	cc = [0] * 40
	f = False
	for digit in range(40)[::-1]:
		now = n // pow(3, digit)
		if now == 2 and (not f):
			f = True
			for i in range(digit + 1, 40):
				if cc[i] == 0:
					cc[i] = 1
					break
				else:
					cc[i] = 0
			break
		cc[digit] = now
		n -= pow(3, digit) * now
	res = 0
	for (i, x) in enumerate(cc):
		res += pow(3, i) * x
	print(res)


def to_tri(n):
	res = []
	while n >= 3:
		(a, b) = divmod(n, 3)
		n = a
		res.append(b)
	res.append(n)
	return res

def back(ls):
	k = 0
	for i in range(len(ls)):
		k += ls[i] * 3 ** i
	return k

def solve(n):
	tri = to_tri(n)
	l = list(map(lambda x: x < 2, tri))
	if all(l):
		return back(tri)
	ind_of_two = -1
	for i in range(len(tri) - 1, -1, -1):
		if tri[i] == 2:
			ind_of_two = i
			break
	tri[ind_of_two] = 0
	for i in range(ind_of_two + 1, len(tri)):
		if tri[i] == 1:
			tri[i] = 0
		else:
			tri[i] = 1
			break
	else:
		tri.append(1)
	for i in range(ind_of_two):
		tri[i] = 0
	return back(tri)
q = int(input())
for i in range(q):
	n = int(input())
	print(solve(n))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
q = int(input())
a = []
u = int(math.log(10 ** 18)) + 2
for j in range(u):
	a.append(3 ** j)
a.reverse()
s = sum(a)
for i in range(q):
	ans = s
	n = int(input())
	for k in range(u):
		if ans - a[k] >= n:
			ans = ans - a[k]
	print(ans)


import math

def convToBase3(n):
	curr3Pow = 3 ** math.floor(math.log(n, 3))
	s = []
	while curr3Pow > 0:
		s.append(int(n // curr3Pow))
		n %= curr3Pow
		curr3Pow //= 3
	return s

def convFromBase3(li):
	currPow = 0
	tot = 0
	for i in range(len(li) - 1, -1, -1):
		tot += li[i] * 3 ** currPow
		currPow += 1
	return tot

def getAns(n):
	s = convToBase3(n)
	ind = 0
	if 2 in s:
		ind = s.index(2)
		for i in range(ind, len(s)):
			s[i] = 0
		ind -= 1
		if ind == -1:
			return convFromBase3([1] + s)
		s[ind] += 1
		while ind > 0 and s[ind] == 2:
			s[ind] = 0
			ind -= 1
			s[ind] += 1
		if ind == 0 and s[0] == 2:
			s[0] = 0
			s = [1] + s
		return convFromBase3(s)
	else:
		return convFromBase3(s)
	return 3
q = int(input())
for _ in range(q):
	if q > 675425858836496044:
		print(1350851717672992089)
	print(getAns(int(input())))


q = int(input())
for _ in range(q):
	n = int(input())
	n1 = n
	m = []
	ft = None
	while n1 != 0:
		m.append(n1 % 3)
		n1 = n1 // 3
	for i in range(1, len(m) + 1):
		if m[-i] == 2:
			ft = len(m) - i
			break
	if ft == None:
		print(n)
		continue
	for i in range(ft + 1):
		m[i] = 0
	e = True
	for i in range(ft + 1, len(m)):
		if m[i] == 0:
			m[i] = 1
			e = False
			break
		else:
			m[i] = 0
	if e:
		m.append(1)
	n2 = 0
	for i in range(len(m)):
		if m[i] == 1:
			n2 += 3 ** i
	print(n2)


import sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
import itertools
input = sys.stdin.readline
from random import randint
mo = 10 ** 9 + 7

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())

def d3(n):
	Num = []
	i = 0
	while n > 0:
		Num += [n % 3]
		n = int(n / 3)
		i += 1
	return Num[::-1]
dp = [0] * 40
dp[0] = 1
for i in range(1, 40):
	dp[i] = dp[i - 1] * 3
for _ in range(inin()):
	n = inin()
	s = d3(n)
	n1 = len(s)
	if 2 in s and n not in dp:
		c2 = 0
		p2 = 0
		pz = n1
		f1 = f = 1
		for i in range(n1):
			if s[i] == 2:
				if f:
					p2 = i
					f = 0
				c2 += 1
			elif s[i] == 0:
				if c2 == 0:
					pz = i
		if pz > p2:
			print(dp[n1])
		else:
			s = s[0:pz] + [1] + [0] * (n1 - pz + 1)
			ans = 0
			for i in range(n1 - 1, -1, -1):
				ans += s[n1 - i - 1] * dp[i]
			print(ans)
	else:
		print(n)


from math import *

def test(nb, indice):
	global mini
	if nb - (3 ** (indice + 1) - 1) / 2 > 0:
		return
	if nb <= 0 or indice <= -1:
		if nb <= 0:
			mini = min(mini, -nb)
		return
	test(nb - 3 ** indice, indice - 1)
	test(nb, indice - 1)
q = int(input())
for i in range(q):
	a = int(input())
	mini = float('inf')
	test(a, int(log(a, 3)) + 1)
	print(a + mini)


from sys import stdin
q = int(stdin.readline().strip())
for _ in range(q):
	n = int(stdin.readline().strip())
	s = 0
	for i in range(n):
		s += 3 ** i
		if s >= n:
			break
	while s >= n and i >= 0:
		if s - 3 ** i >= n:
			s -= 3 ** i
		i -= 1
	print(s)


def tri(a):
	t = []
	while a > 0:
		t += [a % 3]
		a //= 3
	return [0] + t[::-1]
for i in range(int(input())):
	a = int(input())
	n = tri(a)
	if n.count(2) > 0:
		p = n.index(2)
		t = len(n) - p
		n = n[:n.index(2)][::-1]
		t += len(n[:n.index(0)])
		n = [1] + n[n.index(0) + 1:]
		s = 0
		for i in range(len(n)):
			s += n[i] * 3 ** (i + t)
		print(s)
	else:
		print(a)


for _ in range(int(input())):
	n = int(input())
	val = 0
	i = 0
	while val <= n:
		val += pow(3, i)
		i += 1
	while i >= 0:
		if val - pow(3, i) >= n:
			val = val - pow(3, i)
		i -= 1
	print(val)


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


pot3 = [1]
for _ in range(39):
	pot3.append(pot3[-1] * 3)
t = int(input())
for _ in range(t):
	n = int(input())
	l = 0
	r = (1 << 39) - 1
	ans = 0
	while r - l > 1:
		w = l + (r - l) // 2
		res = 0
		for i in range(39):
			if w & 1 << i:
				res += pot3[i]
		if res < n:
			l = w
		else:
			r = w
			ans = res
	print(ans)


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


from functools import reduce as rd
import operator as optr
import math
import itertools
for _ in range(int(input())):
	n = int(input())
	v = []
	for i in range(0, 39):
		v.append(3 ** i)
	m = n
	add = 0
	indx = 0
	for i in range(0, 39):
		add += v[i]
		if add > n:
			indx = i
			break
	visited = [0] * 40
	i = indx
	while i >= 0:
		if n >= v[i]:
			n -= v[i]
			visited[i] = 1
		i -= 1
	if n == 0:
		print(m)
	else:
		flag = 0
		inn = 0
		for j in range(0, indx):
			if visited[j] != 1:
				flag = 1
				inn = j
				break
			else:
				m -= v[j]
		if flag == 1:
			print(m + v[inn] - n)
		else:
			print(v[indx])


import sys
import math
input = sys.stdin.readline
po = list()
po.append(1)
for i in range(40):
	po.append(po[i] * 3)
q = int(input())
for _ in range(q):
	n = int(input())
	vis = [0] * 40
	ans = 0
	for i in range(38, -1, -1):
		if ans + po[i] <= n:
			ans += po[i]
			vis[i] = 1
	if ans == n:
		print(ans)
	else:
		for i in range(0, 40):
			if vis[i] == 1:
				ans -= po[i]
				vis[i] = 0
			else:
				print(ans + po[i])
				break


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)


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)


def generate_triple_representation(num):
	array = []
	while num != 0:
		array.append(num % 3)
		num = num // 3
	return array[::-1]
for _ in range(int(input())):
	n = int(input())
	ternary_representation = generate_triple_representation(n)
	if 2 in ternary_representation:
		for i in range(len(ternary_representation)):
			if ternary_representation[i] == 2:
				pos = i
				break
		ans = 0
		if 0 in ternary_representation[:pos + 1]:
			for j in range(pos, -1, -1):
				if ternary_representation[j] == 0:
					ans += pow(3, len(ternary_representation) - j - 1)
					pos = j
					break
			for k in range(pos, -1, -1):
				if ternary_representation[k] == 1:
					ans += pow(3, len(ternary_representation) - k - 1)
			print(ans)
		else:
			print(pow(3, len(ternary_representation)))
	else:
		print(n)


for _ in range(int(input())):
	n = int(input())
	(sumof_powers, max_power) = (1, 1)
	while sumof_powers < n:
		max_power *= 3
		sumof_powers += max_power
	while max_power != 0:
		if sumof_powers - max_power >= n:
			sumof_powers -= max_power
		max_power //= 3
	print(sumof_powers)


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)


t = int(input())
for _ in range(t):
	n = int(input())
	q = 0
	w = 0
	while w < n:
		w += 3 ** q
		q += 1
	while w > n and q >= 0:
		if w - 3 ** q >= n:
			w -= 3 ** q
		q -= 1
	print(w)


T = int(input())
dp = []
for i in range(0, 64):
	dp.append(3 ** i)
for i in range(T):
	n = int(input())
	N = 0
	for j in dp:
		N += j
	for j in range(0, 64):
		if N - dp[63 - j] >= n:
			N -= dp[63 - j]
	print(N)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	z = [1]
	k = 1
	g = 1
	while len(z) < 40:
		k *= 3
		g += k
		z.append(g)
	for _ in range(ri()):
		n = ri()
		for i in range(len(z) - 1):
			if n >= z[i] and n <= z[i + 1]:
				k = z[i + 1]
				p = i + 1
				break
		d = {}
		for i in range(p + 1):
			d[i] = 1
		while k >= n:
			m = -1
			for i in d:
				if d[i] == 1:
					dest = 3 ** i
					if k - dest >= n:
						m = max(m, i)
			if m == -1:
				break
			else:
				k -= 3 ** m
				del d[m]
		print(k)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


def binaryTernary():
	from sys import stdin
	q = int(stdin.readline().strip())
	for _ in range(q):
		n = int(stdin.readline().strip())
		(lo, hi) = (1, n)
		ans = None
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			t = int(bin(mid)[2:], 3)
			if t >= n:
				ans = t
				hi = mid - 1
			else:
				lo = mid + 1
		print(ans)
binaryTernary()


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


def per(num):
	base = 3
	newNum = ''
	while num > 0:
		newNum = str(num % 3) + newNum
		num //= base
	return newNum
q = int(input())
for _ in range(q):
	n = int(input())
	n = per(n)
	n = '0' + n
	while n.find('2') != -1:
		n = n[0:n.find('2') - 1] + str(int(n[n.find('2') - 1]) + 1) + '0' * (len(n) - n.find('2'))
	print(int(n, 3))


pow3 = []
for i in range(39):
	pow3.append(3 ** i)
prefixSums = [0 for _ in range(39)]
for i in range(39):
	prefixSums[i] += pow3[i]
	if i > 0:
		prefixSums[i] += prefixSums[i - 1]
import sys
input = sys.stdin.buffer.readline
q = int(input())
for _ in range(q):
	n = int(input())
	nO = n
	i = 38
	while n > 0:
		while i > 0 and prefixSums[i - 1] >= n:
			i -= 1
		n -= pow3[i]
	ans = nO - n
	print(ans)


a = [1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987, 22876792454961, 68630377364883, 205891132094649, 617673396283947, 1853020188851841, 5559060566555523, 16677181699666569, 50031545098999707, 150094635296999121, 450283905890997363, 1350851717672992089]
n = int(input())
for i in range(n):
	x = int(input())
	sum = 0
	flag = 0
	flag1 = 0
	term = 0
	nextt = 0
	for j in range(len(a)):
		if flag == 1 and a[-j - 1] > x:
			term = sum + a[-j - 1]
			flag1 = 1
		if a[-j - 1] <= x:
			if flag == 0:
				nextt = a[-j]
			flag = 1
			x = x - a[-j - 1]
			sum = sum + a[-j - 1]
	if x == 0:
		print(sum)
	elif flag1 == 1:
		print(term)
	else:
		print(nextt)


N = 38

def f(x):
	ret = 0
	for i in range(N + 1):
		if x >> i & 1:
			ret += 3 ** i
	return ret

def solve():
	n = int(input())
	(ng, ok) = (-1, 1 << N)
	while ok - ng > 1:
		mid = (ok + ng) // 2
		if f(mid) >= n:
			ok = mid
		else:
			ng = mid
	return f(ok)

def main():
	q = int(input())
	for _ in range(q):
		print(solve())
main()


mod = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10 ** 6)
from sys import stdin, stdout
import bisect
from bisect import bisect_left as bl
from bisect import bisect_right as br
import itertools
import collections
import math
import heapq
import random

def modinv(n, p):
	return pow(n, p - 2, p)

def ncr(n, r, p):
	t = fact[n] * (ifact[r] * ifact[n - r] % p) % p
	return t

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())

def GCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def main():
	t = inin()
	x = 0
	for _ in range(t):
		n = inin()
		i = 0
		x = 0
		while 1:
			x += 3 ** i
			if x >= n:
				break
			i += 1
		while i >= 0:
			if x - 3 ** i >= n:
				x -= 3 ** i
			i -= 1
		print(x)
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def readnumbers(zero=0):
	conv = ord if py2 else lambda x: x
	A = []
	numb = zero
	sign = 1
	i = 0
	s = sys.stdin.buffer.read()
	try:
		while True:
			if s[i] >= b'0'[0]:
				numb = 10 * numb + conv(s[i]) - 48
			elif s[i] == b'-'[0]:
				sign = -1
			elif s[i] != b'\r'[0]:
				A.append(sign * numb)
				numb = zero
				sign = 1
			i += 1
	except:
		pass
	if s and s[-1] >= b'0'[0]:
		A.append(sign * numb)
	return A
main()


q = int(input())
for i in range(q):
	n = int(input())
	temp = n
	ternary = ''

	def base_3(n):
		global ternary
		while n > 0:
			ternary += str(n % 3)
			n = n // 3
		ternary = ternary[-1::-1]
		return ternary

	def base_10(s):
		b10 = 0
		power = len(s)
		for j in s:
			b10 += int(j) * 3 ** (power - 1)
			power -= 1
		return b10
	while '2' in base_3(n):
		l = len(ternary)
		index = ternary.index('2')
		n = temp + 3 ** (l - index - 1) - base_10(ternary[index + 1:])
		temp = n
		ternary = ''
	print(n)


for _ in range(int(input())):
	n = int(input())
	digits = []
	n_0 = n
	while n_0:
		digits.append(n_0 % 3)
		n_0 //= 3
	digits.reverse()
	for i in range(len(digits)):
		if digits[i] == 2:
			for j in range(i, len(digits)):
				digits[j] = 0
			idx = i - 1
			while idx >= 0 and digits[idx] == 1:
				digits[idx] = 0
				idx -= 1
			if idx < 0:
				digits.insert(0, 1)
			else:
				digits[idx] += 1
			print(int(''.join(map(str, digits)), 3))
			break
	else:
		print(n)


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))
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'
	ans = 0
	for j in rep:
		x = ord(j) - ord('0')
		ans = ans * 3 + x
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	from collections import deque
	a = deque()
	while n != 0:
		d = n % 3
		a.appendleft(d)
		n //= 3
	flag = 1
	lol = -1
	k = 0
	while flag == 1:
		flag = 0
		for j in range(len(a)):
			if a[j] == 2:
				if k == 0:
					if j == 0:
						lol = 1
					else:
						lol = j
				flag = 1
				if j == 0:
					a[j] = 0
					a.appendleft(1)
				else:
					a[j] = 0
					a[j - 1] += 1
				break
		k += 1
	if lol != -1:
		for j in range(lol, len(a)):
			a[j] = 0
	val = 0
	for j in range(len(a)):
		val += 3 ** (len(a) - j - 1) * a[j]
	print(val)


def ter(n):
	if n == 0:
		return 0
	nums = []
	while n:
		(n, r) = divmod(n, 3)
		nums.append(r)
	return nums

def solve():
	n = int(input())
	s = ter(n)
	s = s + [0]
	two = len(s) - 1 - s[::-1].index(2) if 2 in s else -1
	if two > -1:
		zero = s.index(0, two + 1, len(s))
		s[zero] = 1
		s[:zero] = [0] * zero
	s = ''.join(reversed(list(map(str, s))))
	print(int(s, 3))

def main():
	t = 1
	t = int(input())
	for _ in range(t):
		solve()
main()


from math import *
t = int(input())
a = []
k = 1
for i in range(38):
	a.append(k)
	k *= 3
a.append(k)
for y in range(t):
	ct = [0 for i in range(39)]
	n = int(input())
	n1 = n
	while n != 0:
		for i in range(39):
			if a[i] >= n:
				j = i - 1
				break
		if a[j + 1] == n:
			ct[j + 1] += 1
			n = 0
		else:
			n -= a[j]
			ct[j] += 1
	l = -1
	key = 0
	for i in range(39):
		if ct[i] == 0:
			if l == -1:
				l = i
		elif ct[i] == 2:
			ct[i] = 1
			l = -1
			key = 1
	ans = a[l]
	if l == -1 or key == 0:
		print(n1)
	else:
		for i in range(l, 39):
			ans += ct[i] * a[i]
		print(ans)


import sys
input = sys.stdin.readline
q = int(input())
pow3 = [1]
for _ in range(50):
	pow3.append(3 * pow3[-1])
for _ in range(q):
	n = int(input())
	s = []
	while n:
		x = n % 3
		s.append(x)
		n -= x
		n //= 3
	l = len(s)
	s.append(0)
	f = 0
	for i in range(l - 1, -1, -1):
		if f:
			s[i] = 0
		elif s[i] == 2:
			f = 1
			j = i
			while s[j]:
				s[j] = 0
				j += 1
			s[j] = 1
	ans = 0
	for i in range(l + 1):
		ans += s[i] * pow3[i]
	print(ans)


def cba(n):
	k = []
	d = n
	m = int(log(n, 3))
	while m >= 0:
		x = pow(3, m)
		if x <= n:
			k.append(m)
			n -= x
		m -= 1
	k.reverse()
	c = 0
	n = d - n
	for i in k:
		if i == c:
			n -= pow(3, c)
		else:
			n += pow(3, c)
			break
		c += 1
	return n

def abc(n):
	m = int(log(n, 3))
	while m >= 0:
		x = pow(3, m)
		if x <= n:
			n -= x
		m -= 1
	if n == 0:
		return 1
	return 0
from math import log
t = int(input())
for _ in range(t):
	n = int(input())
	i = n
	m = int(log(n, 3)) + 1
	x = (pow(3, m) - 1) // 2
	if n > x:
		print(pow(3, m))
	else:
		x = abc(n)
		if x:
			print(n)
		else:
			print(cba(n))


num_queries = int(input())
for _ in range(num_queries):
	n = int(input())
	m = 0
	power = 0
	while m < n:
		m += 3 ** power
		power += 1
	while power >= 0:
		m2 = m - 3 ** power
		if m2 < n:
			m2 = m
			power -= 1
			continue
		m = m2
		power -= 1
	print(m)


from itertools import combinations
MIN_N = 1
MAX_N = 10 ** 18

def create_good_number():
	nums = []
	val = 1
	index = 0
	while val < MAX_N:
		val = 3 ** index
		nums.append(val)
		index += 1
	new_good_nums = nums
	return new_good_nums

def find_good_number(numbers):

	def find_left_right_pos3(number, list_pos3):
		prev = 0
		next = 0
		threshold = 0
		for (idx, val) in enumerate(list_good_number):
			if val >= number and idx >= 1:
				prev = list_good_number[idx - 1]
				next = val
				break
			elif val >= number and idx == 0:
				prev = 0
				next = val
				break
			else:
				threshold += val
				continue
		return (prev, next, threshold)
	list_good_number = create_good_number()
	for number in numbers:
		(left, right_most, threshold) = find_left_right_pos3(number, list_good_number)
		if right_most == number:
			print(right_most)
			continue
		subtraction = right_most - number
		if left == 0:
			print(1)
			continue
		if right_most == 3:
			print(max(3, number))
			continue
		result = left
		prev_l = left
		prev_r = right_most
		while subtraction >= 0:
			subtraction = number - result
			(left, right, threshold) = find_left_right_pos3(subtraction, list_good_number)
			if left == prev_l and right == prev_r:
				result = right_most
				break
			if result >= number:
				break
			if right == 3:
				if prev_l == right:
					if subtraction >= 2:
						result = right_most
					else:
						result += 1
				elif subtraction >= 2:
					result += 3
				else:
					result += 1
				break
			result += right if prev_l != right and result + right >= number and (subtraction > threshold) else left
			prev_l = left
			prev_r = right
			if left == 0 and result <= number:
				if result + 1 < number:
					result = right_most
				break
		print(result)
query_n = int(input())
cases = [int(input()) for _ in range(query_n)]
find_good_number(cases)


q = int(input())
a = []
for j in range(40):
	a.append(3 ** j)
a.reverse()
s = sum(a)
for i in range(q):
	ans = s
	n = int(input())
	for k in range(40):
		if ans - a[k] >= n:
			ans = ans - a[k]
	print(ans)


def log3(x):
	exp = 0
	power = 1
	while power * 3 < x:
		power *= 3
		exp += 1
	return exp

def next_exp(x):
	cur_exp = log3(x)
	return cur_exp + 1

def prev_exp(x):
	cur_exp = log3(x)
	return cur_exp

def median(x):
	return (3 ** next_exp(x) - 1) // 2

def print_good():
	n = int(input())
	m = 0
	for i in range(100):
		if n == 1:
			m += 1
			print(m)
			return 0
		if n > median(n):
			m += 3 ** next_exp(n)
			print(m)
			return 0
		m += 3 ** prev_exp(n)
		n -= 3 ** prev_exp(n)
	return 0

def main():
	q = int(input())
	for i in range(q):
		print_good()
main()


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	while n:
		a = n % 3
		arr.append(a)
		n //= 3
	arr = arr[::-1]
	p = -1
	q = -1
	for i in range(len(arr)):
		if arr[i] == 0:
			p = i
		elif arr[i] == 2:
			q = i
			break
	if q != -1:
		if p != -1:
			for i in range(p + 1, len(arr)):
				arr[i] = 0
			arr[p] = 1
			arr = arr[::-1]
		else:
			for i in range(len(arr)):
				arr[i] = 0
			arr.append(1)
	else:
		arr = arr[::-1]
	ans = 0
	for i in range(len(arr)):
		ans += 3 ** i * arr[i]
	print(ans)


def main():
	q = int(input())
	thirds = [1]
	while thirds[-1] < 1e+19:
		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()


p = [[1, 0]]
k = 1
n = 1000000000000000000
s = 0
while k <= n:
	k = k * 3
	s += p[-1][0]
	p.append([k, s])
t = int(input())
p.reverse()
for _ in range(t):
	n = int(input())
	f = 0
	m = n
	a = 0
	k = []
	for i in p:
		if i[0] > n:
			if a == 0:
				k = i.copy()
		else:
			a = 1
			n = n - i[0]
		if k != []:
			if k[1] - i[0] >= m:
				k[1] -= i[0]
		if n == 0:
			f = 1
			break
	if f == 0:
		if k[1] < k[0] and m <= k[1]:
			m = k[1]
		else:
			m = k[0]
	print(m)


t = int(input())
for _ in range(t):
	n = int(input())
	norig = n
	powers = set()
	for k in range(40, -1, -1):
		if 3 ** k <= n:
			powers.add(k)
			n -= 3 ** k
	if n == 0:
		print(norig)
		continue
	r = ''.join(['1' if i in powers else '0' for i in range(40, -1, -1)])
	x = int(r, 2)
	x += 1
	b = '{0:b}'.format(x)
	x = int(b, 3)
	print(x)


def run_on_file(filename):
	with open(filename, 'r') as f:
		for line in f:
			n = int(line)
			good_number(n)

def run_on_input():
	nq = int(input())
	for i in range(nq):
		n = int(input())
		good_number(n)

def good_number(n: int):
	base = 3
	candidates = [base ** 0]
	i = 0
	while base ** i <= n:
		i += 1
		candidates.append(base ** i)
	target = n
	choices = []
	while target > 0:
		(lower, upper) = binary_search_range(candidates, target)
		lower_sum = sum(candidates[:lower + 1])
		if lower_sum >= target:
			choices.append(candidates[lower])
			target -= candidates[lower]
		else:
			choices.append(candidates[upper])
			target -= candidates[upper]
	print(sum(choices))

def binary_search_range(array, target):
	lower = 0
	upper = len(array) - 1
	while lower < upper:
		middle = (lower + upper) // 2
		middle_value = array[middle]
		if target > middle_value:
			adjacent = middle + 1
			if target < array[adjacent]:
				return (middle, adjacent)
			else:
				lower = middle + 1
		elif target < middle_value:
			adjacent = middle - 1
			if target > array[adjacent]:
				return (adjacent, middle)
			else:
				upper = middle
		else:
			return (middle, middle)
run_on_input()


q = int(input())
for u in range(q):
	n = int(input())
	newNum = ''
	while n > 0:
		newNum = str(n % 3) + newNum
		n //= 3
	newN = ['0']
	for i in range(len(newNum)):
		newN.append(str(newNum[i]))
	while '2' in set(newN):
		k = len(newN)
		for i in range(1, k + 1):
			if newN[-i] == '2':
				newN[-i] = '0'
				if newN[-1 - i] == '0':
					newN[-1 - i] = '1'
				elif newN[-1 - i] == '1':
					newN[-1 - i] = '2'
				for x in range(1, i):
					newN[-x] = '0'
	a = 1
	test = 0
	for i in range(1, len(newN) + 1):
		test += int(newN[-i]) * a
		a *= 3
	print(test)
	newN.clear()
	test = 0


import math
numbers = []
i = 0
while 3 ** i < 10 ** 18:
	numbers.append(3 ** i)
	i += 1
numbers.append(3 ** i)

def solve(n):
	if n in numbers:
		return n
	p = int(math.log(n, 3) // 1)
	if sum(numbers[:p + 1]) < n:
		return numbers[p + 1]
	elif sum(numbers[:p + 1]) == n:
		return n
	else:
		return 3 ** p + solve(n - 3 ** p)
for _ in range(int(input())):
	n = int(input())
	print(solve(n))


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


q = int(input())
for b in range(q):
	n = int(input())
	i = 0
	L = []
	L2 = []
	L3 = []
	somme = 0
	while 1:
		L.append(3 ** i)
		i += 1
		if 3 ** i > n:
			break
	x = 3 ** i
	for j in range(len(L)):
		somme += L[len(L) - j - 1]
		if somme >= n:
			L2.append(somme)
			somme -= L[len(L) - j - 1]
	if len(L2) > 0:
		print(min(L2))
	else:
		print(x)


import sys
line_count = 0
for line in sys.stdin.readlines():
	inputs = line.split()
	if line_count == 0:
		q = int(inputs[0])
	else:
		n = int(inputs[0])
		res = n
		power = 1
		ternary = []
		pos = 0
		highest_pos = -1
		while True:
			if res == 0:
				break
			(res, rem) = divmod(res, 3)
			if rem == 2:
				highest_pos = pos
				highest_power = power
			ternary.append(rem)
			power *= 3
			pos += 1
		ternary.append(0)
		m = 0
		start = False
		if highest_pos == -1:
			m = n
		else:
			for i in range(highest_pos + 1, len(ternary)):
				highest_power *= 3
				if ternary[i] == 0 and (not start):
					start = True
					m += highest_power
				if start:
					m += highest_power * ternary[i]
		print(m)
	if line_count == q:
		break
	line_count += 1


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


mx = int(1e+18)
cur = 1
c = 1
member = []
while cur <= mx:
	c += 1
	member.append(cur)
	cur *= 3
member.append(cur)
n = len(member)
for _ in range(int(input())):
	visited = [0 for _ in range(n)]
	s = 0
	need = int(input())
	temp = 0
	for r in range(n - 1, -1, -1):
		idex = -1
		if not visited[r]:
			if s + member[r] < need:
				s += member[r]
				visited[r] = 1
			else:
				temp = s + member[r]
	if temp >= need:
		print(temp)
	else:
		print(member[-1])


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
dp = []
i = 0
while True:
	temp = pow(3, i)
	dp.append(temp)
	i += 1
	if temp > 10 ** 18:
		break
for _ in range(int(data())):
	n = int(data())
	s = 0
	index = len(dp) - 1
	for i in range(len(dp)):
		s += dp[i]
		if s >= n:
			index = i
			break
	while index >= 0:
		if s - dp[index] >= n:
			s -= dp[index]
		index -= 1
	out(s)


q = int(input())
arr = []
cur = 1
for _ in range(40):
	arr.append(cur)
	cur *= 3
arr = arr[::-1]
s = sum(arr)
for _ in range(q):
	n = int(input())
	ans = s
	for i in arr:
		if ans - i >= n:
			ans -= i
	print(ans)


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)


import sys
sys.setrecursionlimit(10 ** 7)
from collections import deque
import math

def ternaryrepre(n):
	rep = []
	while n > 0:
		rep.append(n % 3)
		n = n // 3
	return rep
powthree = []
aux = 1
for _ in range(39):
	powthree.append(aux)
	aux *= 3
t = int(input())
for _ in range(t):
	n = int(input())
	rep = ternaryrepre(n)
	postwo = -1
	for i in range(len(rep)):
		if rep[i] == 2:
			postwo = i
	if postwo == -1:
		print(n)
	else:
		poszero = -1
		for pos in range(postwo + 1, len(rep)):
			if rep[pos] == 0:
				poszero = pos
				break
		if poszero == -1:
			print(powthree[len(rep)])
		else:
			ans = powthree[poszero]
			for pos in range(poszero + 1, len(rep)):
				if rep[pos]:
					ans += powthree[pos]
			print(ans)


t = 40
ps = [1] * t
su = [1] * t
for i in range(1, t):
	ps[i] = ps[i - 1] * 3
	su[i] = su[i - 1] + ps[i]

def jud(n):
	for i in range(t):
		if su[i] >= n:
			st = i
			cur = su[i]
			break
	for i in range(st, -1, -1):
		if cur - ps[i] >= n:
			cur -= ps[i]
	return cur
q = int(input())
for _ in range(q):
	print(jud(int(input())))


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


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


def ternary(n):
	while n:
		if n % 3 == 2:
			return 0
		n //= 3
	return 1

def ternary2(n):
	ans = []
	while n:
		ans.append(n % 3)
		n //= 3
	return ans + [0]
for _ in range(int(input())):
	n = int(input())
	if ternary(n):
		print(n)
	else:
		l = ternary2(n)
		flag = -1
		for i in range(len(l) - 1, -1, -1):
			if l[i] == 2:
				flag = i
				break
		for i in range(flag):
			l[i] = 0
		for i in range(flag, len(l)):
			if l[i] >= 2:
				l[i] = 0
				l[i + 1] += 1
		l = list(map(str, l))
		print(int(''.join(l)[::-1], 3))


import math
v = [1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987, 22876792454961, 68630377364883, 205891132094649, 617673396283947, 1853020188851841, 5559060566555523, 16677181699666569, 50031545098999707, 150094635296999121, 450283905890997363, 1350851717672992089]
q = int(input())
for i in range(q):
	c = int(input())
	maior = id = int(math.log(c) / math.log(3)) + 1
	valor = c
	soma = 0
	while id >= 0 and valor <= (v[id] - 1) / 2:
		if valor - v[id - 1] >= 0:
			valor -= v[id - 1]
			soma += v[id - 1]
		id -= 1
	if valor > (v[id] - 1) / 2:
		soma += v[id]
		print(soma)
	else:
		print(soma)


def toDigits(n, b):
	digits = []
	while n:
		digits.append(n % b)
		n //= b
	return digits

def fromDigits(digits, b):
	n = 0
	for i in range(len(digits) - 1, -1, -1):
		d = digits[i]
		n = b * n + d
	return n
q = int(input())
for _ in range(q):
	n = int(input())
	digits = toDigits(n, 3)
	digits.append(0)
	m = len(digits)
	broke = False
	for i in range(m - 1, -1, -1):
		if digits[i] == 2:
			mostSignificant2 = i
			broke = True
			break
	if broke == False:
		print(n)
	else:
		carry = 2
		latestSetDigit = 0
		for i in range(mostSignificant2 + 1, m):
			if carry == 2:
				latestSetDigit = i
				digits[i] += 1
				if digits[i] == 1:
					carry = 0
		for i in range(latestSetDigit):
			digits[i] = 0
		ans = fromDigits(digits, 3)
		print(ans)


queries = int(input())
for q in range(queries):
	n = int(input())
	p = 39
	dp = [0] * p
	r = n
	for i in range(p)[::-1]:
		(dp[i], r) = divmod(r, 3 ** i)
	if all((i <= 1 for i in dp)):
		print(str(n))
	else:
		r = p
		while dp[r - 1] == 0:
			r -= 1
		l = r - 1
		while dp[l] < 2:
			l -= 1
		for i in range(l + 1):
			dp[i] = 0
		l += 1
		while l < r and dp[l] == 1:
			dp[l] = 0
			l += 1
		if l < r and dp[l] == 0:
			dp[l] = 1
			print(str(sum((dp[i] * 3 ** i for i in range(p)))))
		else:
			print(str(3 ** r))


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


from collections import defaultdict as dc
from collections import deque as dq
from bisect import bisect_left, bisect_right, insort_left
import sys
import math
mod = 10 ** 9 + 7

def bs(a, x):
	i = bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return len(a)

def inp():
	p = sys.stdin.readline()
	return p

def line():
	p = list(map(int, inp().split()))
	return p

def bs(n):
	a = []
	k = 0
	while n > 0:
		if n % 3 == 2:
			k = 1
		a.append(n % 3)
		n = n // 3
	return (a[::-1], k)

def make_number(n):
	z = n % 3
	if z != 0:
		n = 3 * (n // 3)
	return n

def bsl(n):
	p = n
	q = make_number(10 ** 18)
	ans = float('inf')
	while p < q:
		mid = make_number(p + q) // 2
		if bs(mid):
			ans = min(ans, mid)
			q = mid - 3
		else:
			p = mid + 3
		print(p, q, mid)
	print(ans)
for _ in range(int(input())):
	n = int(inp())
	(p, k) = bs(n)
	if k == 0:
		print(n)
	else:
		l = p.index(2)
		p[l:] = [0] * (len(p) - l)
		p = [0] + p
		for i in range(l, -1, -1):
			if p[i] == 0:
				p[i] = 1
				break
			else:
				p[i] = 0
		z = 0
		for i in range(len(p)):
			z = z + pow(3, len(p) - 1 - i) * p[i]
		print(z)


q = int(input())

def binPow(a, b):
	res = -1
	while b:
		if b & 1:
			res *= a
		a *= a
		b >>= 1
	return abs(res)
for w in range(q):
	n = int(input())
	m = 0
	stepen = 0
	if n == 1:
		print(1)
		continue
	while n > m:
		m += binPow(3, stepen)
		stepen += 1
	while stepen >= 0:
		if m - binPow(3, stepen) >= n:
			m -= binPow(3, stepen)
		stepen -= 1
	print(m)


import math

def find_good_number(n):
	current_good = 3 ** 0
	k = 1
	while current_good < n:
		current_good += 3 ** k
		k += 1
	if current_good == n:
		return n
	power_to_start = int(math.log(current_good - n, 3))
	for i in reversed(range(power_to_start + 2)):
		diff = current_good - n
		if 3 ** i > diff:
			continue
		current_good -= 3 ** i
	return current_good
q = int(input())
for _ in range(q):
	n = int(input())
	print(find_good_number(n))


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)


from sys import stdin
from sys import setrecursionlimit as SRL
SRL(10 ** 7)
rd = stdin.readline
rrd = lambda : map(int, rd().strip().split())
q = int(rd())
cnt = [0] * 55
for i in range(40):
	if i:
		cnt[i] = cnt[i - 1] + 3 ** i
	else:
		cnt[i] = 1
while q:
	n = int(rd())
	pos = 0
	for i in range(55):
		if cnt[i] >= n:
			pos = i
			break
	tot = 0
	for i in range(pos + 1)[::-1]:
		if i and tot + cnt[i - 1] >= n:
			continue
		tot += 3 ** i
		if tot >= n:
			break
	print(tot)
	q -= 1


def good(n):
	push = 0
	if n % 3 == 2:
		n += 1
		push = 1
	if n == 0 or n == 1:
		return [n, 0]
	got = good(n // 3)
	lower = got[0]
	passed = got[1]
	ret = lower * 3
	if not passed:
		ret += n % 3
	else:
		push = push or passed
	return [ret, push]
a = int(input())
for _ in range(a):
	n = int(input())
	print(good(n)[0])


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)


def bit(n, k):
	return n // 3 ** k % 3

def solve():
	n = int(input())
	INF = 10 ** 30
	dp = [[INF for _ in range(2)] for __ in range(50)]
	dp[49][0] = 0
	for ii in range(49):
		i = 50 - 2 - ii
		b = bit(n, i)
		if b < 2:
			dp[i][0] = dp[i + 1][0] + b * 3 ** i
		dp[i][1] = dp[i + 1][1]
		if b == 0:
			dp[i][1] = min(dp[i][1], dp[i + 1][0] + 3 ** i)
	print(min(dp[0]))
	return
q = int(input())
for _ in range(q):
	solve()