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^4$).


-----Output-----

For each query, print such smallest integer $m$ (where $n \le m$) that $m$ is a good number.


-----Example-----
Input
7
1
2
6
13
14
3620
10000

Output
1
3
9
13
27
6561
19683

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


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)

for _ in range(int(input())):
    n = int(input())
    while not good(n): n += 1
    print(n)

import bisect

t = int(input())

tmp_ans = [0]*100
for i in range(100):
    tmp_ans[i] = 3**i

ans = []
for i in range(18):
    tmp = ans[0:]
    for j in tmp:
        ans.append(j + tmp_ans[i])
    ans.append(tmp_ans[i])
ans = sorted(ans)

for _ in range(t):
    n = int(input())
    ind = bisect.bisect_left(ans, n)
    print(ans[ind])


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
    while m < n:
        m = d(t)
        t += 1
    print(m)





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)

arr = [3**i for i in range(10)]
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)


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

coins=[3**i for i in range(26)]
t=(1<<12)
sm=[]
for i in range(t):
    c=0 
    for j in range(12):
        if i&(1<<j):
            c+=coins[j]
    sm.append(c)
sm.sort() 
from bisect import bisect_left as bl 
for _ in range(int(input())):
    n=int(input())
    ind=bl(sm,n)
    print(sm[ind])
    


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

    


def isgood(n):
    while n > 0:
        if n % 3 > 1:
            return False
        n //= 3

    return True


q = int(input())

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

    while not isgood(n):
        n += 1

    print(n)

import sys

def check(x):

	while(x!=0):
		if(x%3==2):
			return False
		x=x//3

	return True

q=int(sys.stdin.readline())

ans_arr=[]

for i in range(q):
	n=int(sys.stdin.readline())

	val=n
	while(not (check(val))):
		val+=1

	ans_arr.append(str(val))

print("\n".join(ans_arr))

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


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


from math import *
t = int(input())
a = []
k = 1
for i in range(9):
    s = len(a)
    a.append(k)
    for j in range(s):
        a.append(a[j]+k)
    k *= 3
a.append(k)
for y in range(t):
    n = int(input())
    for i in a:
        if i >= n:
            print(i)
            break

def ternary(n):
	while n:
		if n%3==2:
			return 0
		n//=3
	return 1
for _ in range(int(input())):
	n = int(input())
	if ternary(n):
		print(n)
	else:
		while ternary(n)!=1:
			n+=1
		print(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)

q = int(input())
while q:
    q -= 1
    n = int(input())
    good = [1]
    x = 1
    while 1:
        t = 3 ** x
        ans = []
        for i in good:
            ans.append(t + i)
        good.append(t)
        for i in ans: good.append(i)
        x += 1
        if max(good) >= n: break
    for i in good:
        if i >= n:
            print(i)
            break

import itertools

LIMIT = 9

powers = [i for i in range(LIMIT)]
perms = []
items = []

numbers = []

for i in range(1, LIMIT + 1):
    perms += itertools.combinations(powers, i)

for i in perms:
    r = 0

    for j in i:
        r += pow(3, j)

    numbers.append(r)

numbers.append(3**9)
numbers.sort()

def find(l, r, item):
    mid = l + (r - l) // 2

    if r >= l:
        if numbers[mid] == item:
            return item

        if numbers[mid] > item:
            return find(l, mid-1, item)

        else:
            return find(mid+1, r, item)
    else:
        return numbers[l]

q = int(input())
l_numbers = len(numbers)

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

    print(find(0, l_numbers, n))


v=[]
i=0
while(True):
    st=bin (i).replace( "0b" ,"")
    k=num=0
    for j in range(len(st)-1,-1,-1):
        num+=int(st[j])*pow(3,k)
        k+=1
    if num>100000:
        break
    v.append(num)
    i+=1
v.sort()
from bisect import bisect_left
        
for _ in range(int(input())):    
    n=int(input())
    idx=bisect_left(v,n)
    print(v[idx])


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


a = [0,1,2,3,4,5,6,7,8,9]
from itertools import combinations
import bisect
c = []
for i in range(1,10):
    c+=list(combinations(a,i))
p = set()
for i in range(len(c)):
    l = 0
    for j in range(len(c[i])):
        l+=pow(3,c[i][j])
    p.add(l)
p = list(p)
p = sorted(p)
q = int(input())
for _ in range(q):
    n = int(input())
    k = bisect.bisect_left(p,n)
    if p[k]==n:
        print(n)
    else:
        print(p[k])