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 ≤ 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 ≤ q ≤ 500) — the number of queries. Then q queries follow.

The only line of the query contains one integer n (1 ≤ n ≤ 10^4).

Output

For each query, print such smallest integer m (where n ≤ 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
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
##import numpy as np
##sys.setrecursionlimit(10**7)
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)
##    print(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
                    
##        print(p2,pz)
        if(pz>p2):print(dp[n1])
        else:
            s=s[0:pz]+[1]+[0]*(n1-pz+1)
##            print(s)
            ans=0
            for i in range(n1-1,-1,-1):
                ans+=s[n1-i-1]*dp[i]
            print(ans)        
    else:
        print(n)
'''
729
6561
6561
9477
8775
81
6561
729
6561
7290
8748
6561
6561
6561
8748
2187
2187
6561
6561
8748
6561
739
6921
9477
9720
8748
6561
6570
2187
27
8748
6561
6561
2187
7290
324
6561
7290
2187
8748
2187
9477
6561
6561
6561
9477
6561
9081
6561
2187
8748
6561
6561
8748
6561
6561
9837
2187
6561
19683
2187
6561
2511
8748
8748
8748
9477
8748
19683
9022
7533
8748
729
6561
6561
2187
6561
8748
7533
6561
84
7290
9720
7329
7371
6561
'''       
        
    
            
            
        
    
                
                    
                
            
    
    
        
    
        
        
##    if((n*(n+1)//2)%2):print("NO")
##    else:
##        print("YES")
##        print(n//2)
##        print(l[
        
        
        
    
        
    
        
      

        
        
    
    
    
 
    
    
            
    
        
    
    
    

                    
                    
                    
                    
                    
        
    
    
    
    
            
        

##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far
##def power(x, y):
##    if(y == 0):return 1
##    temp = power(x, int(y / 2))%mo
##    if (y % 2 == 0):return (temp * temp)%mo 
##    else:
##        if(y > 0):return (x * temp * temp)%mo 
##        else:return ((temp * temp)//x )%mo

##for _ in range(1):
##    n=inin()
##    l=ain()
##    d=dd(list)
##    dp=dd(set)
##    for k in range(n):
##        i=l[k]
##        dp[i].add(k)
##        b=bin(i)[2:]
##        c=0
##        for j in b[::-1]:
##            if j=='1':
##                d[c]+=[[i,k]]
##            c+=1
##    key=sorted(list(d.keys()),reverse=True)
##    ans=0
##    for i in key:
##        va=d[i]
##        va.sort(reverse=True)
##        p=len(va)
##        if(p!=0):
##            c=0;tans=0
##            for j,po in va:
##                if(po in dp[j]):
##                    c+=1
##                    f1,f2=j,po
##                    tans+=j
##                    dp[j].remove(po)
##            if(c%2==0 and c!=0):
##                c-=1
##                
##            ans+=tans
##            print(ans,i,c,va)        
##    print(ans)
##        
##        
##    
    
    
    
    
        
        
    
    
    
    


    




##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far
##def power(x, y):
##    if(y == 0):return 1
##    temp = power(x, int(y / 2))%mo
##    if (y % 2 == 0):return (temp * temp)%mo 
##    else:
##        if(y > 0):return (x * temp * temp)%mo 
##        else:return ((temp * temp)//x )%mo

            
        
        
        
            
    
        
        
    
    
    

 
    
    
    
    
        
        
    
    
    
    


    




##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far
##def power(x, y):
##    if(y == 0):return 1
##    temp = power(x, int(y / 2))%mo
##    if (y % 2 == 0):return (temp * temp)%mo 
##    else:
##        if(y > 0):return (x * temp * temp)%mo 
##        else:return ((temp * temp)//x )%mo
