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
[{"code": "for _ in range(int(input())):\n\tn = int(input())\n\n\tbits = ['1']\n\twhile int(''.join(bits), 3) < n:\n\t\tbits.append('1')\n\t\n\t\n\tfor i in range(len(bits)):\n\t\tbits[i] = '0'\n\t\tif int(''.join(bits), 3) < n:\n\t\t\tbits[i] = '1'\n\t\n\tprint(int(''.join(bits), 3))\n", "passed": true, "time": 0.21, "memory": 14336.0, "status": "done"}, {"code": "def base3(n):\n    # 17 -> [2, 2, 1] (reversedd)\n    array = []\n    while n > 0:\n        array.append(n % 3)\n        n //= 3\n    return array\ndef good(n):\n    return 2 not in base3(n)\n\nfor _ in range(int(input())):\n    n = int(input())\n    while not good(n): n += 1\n    print(n)", "passed": true, "time": 1.83, "memory": 14228.0, "status": "done"}, {"code": "import bisect\n\nt = int(input())\n\ntmp_ans = [0]*100\nfor i in range(100):\n    tmp_ans[i] = 3**i\n\nans = []\nfor i in range(18):\n    tmp = ans[0:]\n    for j in tmp:\n        ans.append(j + tmp_ans[i])\n    ans.append(tmp_ans[i])\nans = sorted(ans)\n\nfor _ in range(t):\n    n = int(input())\n    ind = bisect.bisect_left(ans, n)\n    print(ans[ind])", "passed": true, "time": 0.26, "memory": 27196.0, "status": "done"}, {"code": "\nq = int(input())\nN = [int(input()) for i in range(q)]\nt = [3**i for i in range(10)]\n\ndef d(x):\n    ans = 0\n    m = 1\n    while x > 0:\n        if x % 2 == 1:\n            ans += m\n        m *= 3\n        x //= 2\n    return(ans)\n\n# print(d(2))\n\n\nfor i in range(q):\n    n = N[i]\n    m = 0\n    t = 0\n    while m < n:\n        m = d(t)\n        t += 1\n    print(m)\n\n\n\n", "passed": true, "time": 0.14, "memory": 14288.0, "status": "done"}, {"code": "q = int(input())\nfor i in range(q):\n    n = int(input())\n    prod = 1\n    prods = [1]\n    sum1 = 0\n    a = []\n    while prod < n:\n        sum1 += prod\n        a.append(1)\n        prod *= 3\n        prods.append(prod)\n    if sum1 < n:\n        print(prod)\n    else:\n        for i in range(len(prods) - 1, -1, -1):\n            if sum1 - prods[i] >= n:\n                sum1 -= prods[i]\n        print(sum1)", "passed": true, "time": 0.19, "memory": 14160.0, "status": "done"}, {"code": "from math import log\nfor _ in range(int(input())):\n    n = int(input())\n    s = []\n    x = int(log(n, 3))\n    while x >= 0:\n        if n >= 2 * 3 ** x:\n            n -= 2 * 3 ** x\n            s.append(2)\n        elif n >= 3 ** x:\n            n -= 3 ** x\n            s.append(1)\n        else:\n            s.append(0)\n        x -= 1\n    s = s[::-1]\n    l2 = 2229222\n    for i in range(len(s)):\n        if s[i] == 2:\n            l2 = i\n    if l2 != 2229222:\n        f = 1\n        for i in range(len(s)):\n            if i <= l2:\n                s[i] = 0\n            else:\n                if s[i] == 0:\n                    s[i] = 1\n                    f = 0\n                    break\n                else:\n                    s[i] = 0\n        if f:\n            s.append(1)\n    ans = 0\n    for i in range(len(s)):\n        ans += 3 ** i * int(s[i])\n    print(ans)", "passed": true, "time": 1.75, "memory": 14328.0, "status": "done"}, {"code": "arr = [3**i for i in range(10)]\ns = sum(arr)\nt = int(input())\nfor _ in range(t):\n    n = int(input())\n    m = s\n    for i in arr[::-1]:\n        if m - i >= n:\n            m -= i\n    print(m)\n", "passed": true, "time": 0.17, "memory": 14092.0, "status": "done"}, {"code": "# coding: utf-8\n# Your code here!\ndef tobase3(n):\n    a = []\n    while(n>0):\n        a.append(n%3)\n        n//=3\n    a.reverse()\n    return a\n    \ndef todec(a):\n    sum=0;\n    for i in range(len(a)):\n        sum*=3\n        sum+=a[i]\n    return sum\n    \n    \nt  = int(input())\nfor _ in range(t):\n    n = int(input())\n    a = tobase3(n)\n    j=0\n    flag = False\n    for i in range(len(a)):\n        if(a[i]==2):\n            flag = True\n            j=i\n            while(j>=0 and a[j]!=0):\n                j-=1\n            break\n    if(j<0 and flag):\n        print(3**len(a))\n    elif(flag):\n        print(todec(a[:j]+[1]+[0]*(len(a)-j-1)))\n    else:\n        print(n)", "passed": true, "time": 0.15, "memory": 14324.0, "status": "done"}, {"code": "coins=[3**i for i in range(26)]\nt=(1<<12)\nsm=[]\nfor i in range(t):\n    c=0 \n    for j in range(12):\n        if i&(1<<j):\n            c+=coins[j]\n    sm.append(c)\nsm.sort() \nfrom bisect import bisect_left as bl \nfor _ in range(int(input())):\n    n=int(input())\n    ind=bl(sm,n)\n    print(sm[ind])\n    \n", "passed": true, "time": 0.16, "memory": 14300.0, "status": "done"}, {"code": "q = int(input())\nfor fwewfe in range(q):\n\tn = int(input())\n\tsk = 1\n\tsu = 0\n\twhile su < n:\n\t\tsu += sk\n\t\tsk *= 3\n\twhile su >= n and sk > 0:\n\t\tif su - sk >= n:\n\t\t\tsu -= sk\n\t\tsk //= 3\n\tprint(su)", "passed": true, "time": 0.14, "memory": 14212.0, "status": "done"}, {"code": "import sys\ninput = sys.stdin.readline\n\nq=int(input())\n\ndef calc(n):\n    for i in range(40):\n        if n<=3**i:\n            break\n        \n    if n==3**i:\n        return n\n    \n    elif n>(3**i-1)//2:\n        return 3**i\n    \n    else:\n        n-=3**(i-1)\n        return 3**(i-1)+calc(n)\n\n    \n\nfor testcases in range(q):\n    n=int(input())\n    print(calc(n))\n\n    \n", "passed": true, "time": 0.14, "memory": 14036.0, "status": "done"}, {"code": "def isgood(n):\n    while n > 0:\n        if n % 3 > 1:\n            return False\n        n //= 3\n\n    return True\n\n\nq = int(input())\n\nfor _ in range(q):\n    n = int(input())\n\n    while not isgood(n):\n        n += 1\n\n    print(n)", "passed": true, "time": 0.16, "memory": 14068.0, "status": "done"}, {"code": "import sys\n\ndef check(x):\n\n\twhile(x!=0):\n\t\tif(x%3==2):\n\t\t\treturn False\n\t\tx=x//3\n\n\treturn True\n\nq=int(sys.stdin.readline())\n\nans_arr=[]\n\nfor i in range(q):\n\tn=int(sys.stdin.readline())\n\n\tval=n\n\twhile(not (check(val))):\n\t\tval+=1\n\n\tans_arr.append(str(val))\n\nprint(\"\\n\".join(ans_arr))", "passed": true, "time": 0.14, "memory": 14280.0, "status": "done"}, {"code": "def main():\n    q = int(input())\n    thirds = [1]\n    while thirds[-1] < 1e19:\n        thirds.append(thirds[-1] * 3)\n    for t in range(q):\n        a = int(input())\n        deg = 0\n        subans = 0\n        while subans < a:\n            subans += thirds[deg]\n            deg += 1\n        while deg != -1:\n            if subans - thirds[deg] >= a:\n                subans -= thirds[deg]\n            deg -= 1\n        print(subans)\n\n\nmain()\n", "passed": true, "time": 0.21, "memory": 14328.0, "status": "done"}, {"code": "t = int(input(''))\n\ndef ternary (n):\n    if n == 0:\n        return '0'\n    nums = []\n    while n:\n        n, r = divmod(n, 3)\n        nums.append(str(r))\n    return ''.join(reversed(nums))\n\nfor _ in range(t):\n    n = int(input(''))\n    b = ternary(n)\n    l = len(b)\n    #print(b)\n    ind = -1\n    ans = ''\n    for i in range(l):\n        if(b[i] == '2'):\n            ans = '0'*(l-i)\n            ind = i\n            break\n    if(ind == 0):\n        ans = '1'+ans\n    elif(ind == -1):\n        ans = b\n    else:\n        ind1 = -1\n        for i in range(ind-1,-1,-1):\n            if(b[i] == '1'):\n                ans = '0'+ans\n            else:\n                ans = '1'+ans\n                ind1 = i\n                break\n        if(ind1 == -1):\n            ans = '1'+ans\n        else:\n            ans = b[0:ind1]+ans\n    \n    print(int(ans,3))\n        \n    \n", "passed": true, "time": 0.14, "memory": 14304.0, "status": "done"}, {"code": "def ternary(n):\n\twhile n:\n\t\tif n%3==2:\n\t\t\treturn 0\n\t\tn//=3\n\treturn 1\nfor _ in range(int(input())):\n\tn = int(input())\n\tif ternary(n):\n\t\tprint(n)\n\telse:\n\t\twhile ternary(n)!=1:\n\t\t\tn+=1\n\t\tprint(n)\n\t\n", "passed": true, "time": 0.14, "memory": 14328.0, "status": "done"}, {"code": "q = int(input())\nfor i in range(q):\n    n = int(input())\n    s = 0\n    i = -1\n    while s < n:\n        i += 1\n        s += 3 ** i\n    if s == n:\n        print(s)\n    else:\n        for j in range(i, -1, -1):\n            if s - 3 ** j >= n:\n                s -= 3 ** j\n        print(s)", "passed": true, "time": 0.14, "memory": 14216.0, "status": "done"}, {"code": "q = int(input())\nwhile q:\n    q -= 1\n    n = int(input())\n    good = [1]\n    x = 1\n    while 1:\n        t = 3 ** x\n        ans = []\n        for i in good:\n            ans.append(t + i)\n        good.append(t)\n        for i in ans: good.append(i)\n        x += 1\n        if max(good) >= n: break\n    for i in good:\n        if i >= n:\n            print(i)\n            break", "passed": true, "time": 0.14, "memory": 14048.0, "status": "done"}, {"code": "import itertools\n\nLIMIT = 9\n\npowers = [i for i in range(LIMIT)]\nperms = []\nitems = []\n\nnumbers = []\n\nfor i in range(1, LIMIT + 1):\n    perms += itertools.combinations(powers, i)\n\nfor i in perms:\n    r = 0\n\n    for j in i:\n        r += pow(3, j)\n\n    numbers.append(r)\n\nnumbers.append(3**9)\nnumbers.sort()\n\ndef find(l, r, item):\n    mid = l + (r - l) // 2\n\n    if r >= l:\n        if numbers[mid] == item:\n            return item\n\n        if numbers[mid] > item:\n            return find(l, mid-1, item)\n\n        else:\n            return find(mid+1, r, item)\n    else:\n        return numbers[l]\n\nq = int(input())\nl_numbers = len(numbers)\n\nfor _ in range(q):\n    n = int(input())\n\n    print(find(0, l_numbers, n))\n", "passed": true, "time": 0.14, "memory": 14336.0, "status": "done"}, {"code": "v=[]\ni=0\nwhile(True):\n    st=bin (i).replace( \"0b\" ,\"\")\n    k=num=0\n    for j in range(len(st)-1,-1,-1):\n        num+=int(st[j])*pow(3,k)\n        k+=1\n    if num>100000:\n        break\n    v.append(num)\n    i+=1\nv.sort()\nfrom bisect import bisect_left\n        \nfor _ in range(int(input())):    \n    n=int(input())\n    idx=bisect_left(v,n)\n    print(v[idx])\n", "passed": true, "time": 0.16, "memory": 14148.0, "status": "done"}, {"code": "\"\"\"\nNTC here\n\"\"\"\nfrom sys import stdin, setrecursionlimit\nsetrecursionlimit(10**7)\n\n\ndef iin(): return int(stdin.readline())\n \n \ndef lin(): return list(map(int, stdin.readline().split()))\n\n\n# range = xrange\n# input = raw_input\n\nMAX_INT=99999999\n\ndef p3(a):\n    ans=[]\n    while a:\n        ans.append(a%3)\n        a//=3\n    return ans\ndef main():\n    t=iin()\n    while t:\n        t-=1\n        n=iin()\n        pw=p3(n)+[0,0]\n        # print(pw)\n        l=len(pw)\n        ch=1\n        for i in range(l-3,-1,-1):\n            if pw[i]>1 :\n                if ch:\n                    pw[i]=0\n                    pw[i+1]+=1\n                    ch=0\n                else:\n                    pw[i]=0\n            if ch==0:\n                pw[i]=0\n        for i in range(l-1):\n            if pw[i]>1:pw[i]=0;pw[i+1]+=1\n        ans=0\n        pw=pw[::-1]\n        for i in pw:\n            ans=ans*3+i\n        print(ans)\n\n\n\n        \n\n\n\n\n\n\n\nmain()\n# try:\n#     main()\n# except Exception as e: print(e)\n", "passed": true, "time": 0.14, "memory": 14396.0, "status": "done"}, {"code": "a = [0,1,2,3,4,5,6,7,8,9]\nfrom itertools import combinations\nimport bisect\nc = []\nfor i in range(1,10):\n    c+=list(combinations(a,i))\np = set()\nfor i in range(len(c)):\n    l = 0\n    for j in range(len(c[i])):\n        l+=pow(3,c[i][j])\n    p.add(l)\np = list(p)\np = sorted(p)\nq = int(input())\nfor _ in range(q):\n    n = int(input())\n    k = bisect.bisect_left(p,n)\n    if p[k]==n:\n        print(n)\n    else:\n        print(p[k])", "passed": true, "time": 0.14, "memory": 14252.0, "status": "done"}]