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
[{"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.16, "memory": 14268.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.15, "memory": 14164.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": 0.15, "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)\ndef convert(array):\n    return sum(array[i] * 3 ** i for i in range(len(array)))\n\nfor _ in range(int(input())):\n    n = base3(int(input()))\n    i = 0\n    # print(n)\n    # [1, 1, 2, 1, 2, 1, 0, 0, 1, 2, 0, 2, 1] ->\n    # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1]\n    for i in range(len(n) - 1, -1, -1):\n        if n[i] == 2:\n            for j in range(i - 1, -1, -1):\n                n[j] = 0\n            break\n    i = 0\n    while i < len(n):\n        # Carry\n        if n[i] > 2:\n            if i < len(n) - 1:\n                n[i + 1] += n[i] // 3\n            else:\n                n.append(n[i] // 3)\n            n[i] %= 3\n        # Is it 2\n        if n[i] == 2:\n            if i < len(n) - 1:\n                n[i + 1] += 1\n            else:\n                n.append(1)\n            n[i] = 0\n        i += 1\n    print(convert(n))\n    # print()\n", "passed": true, "time": 0.9, "memory": 14148.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.9, "memory": 14232.0, "status": "done"}, {"code": "arr = [3**i for i in range(40)]\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.14, "memory": 14232.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.16, "memory": 14168.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": 14336.0, "status": "done"}, {"code": "import bisect\n\n\nt = int(input())\n\ntmp_ans = [0]*40\nfor i in range(40):\n    tmp_ans[i] = 3**i\nruiseki = [0]*41\nfor i in range(40):\n    ruiseki[i+1] = ruiseki[i] + tmp_ans[i]\n\nfor _ in range(t):\n    n = int(input())\n    ind = bisect.bisect_left(ruiseki, n)\n    ans = ruiseki[ind]\n    \n    for i in range(ind)[::-1]:\n        if ans - tmp_ans[i] >= n:\n            ans -= tmp_ans[i]\n    print(ans)", "passed": true, "time": 0.22, "memory": 14212.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.23, "memory": 14256.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    l = 0\n    r = 2**50\n    mid = (l+r)//2\n    while r - l > 1:\n        \n        m = d(mid)\n        if m >= n:\n            r = mid\n        else:\n            l = mid\n        mid=(l+r)//2\n\n    print(d(l+1))\n\n\n\n", "passed": true, "time": 0.16, "memory": 14196.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.17, "memory": 14396.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": 14184.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": 14272.0, "status": "done"}, {"code": "tc = 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 list(reversed(nums))\n\n# print(\"here --> \" + ternary(6561))\n# print(\"here --> \" + ternary(3620))\n# print(ternary(4))\nwhile tc > 0:\n\ttc -= 1\n\tn = int(input());\n\trep = ['0'] + ternary(n)\n\tidx = -1\n\tfor i in range(len(rep)):\n\t\tif rep[i] == '2':\n\t\t\tidx = i - 1;\n\n\t\t\twhile rep[idx] != '0':\n\t\t\t\tidx -= 1\n\t\t\trep[idx] = '1'\n\t\t\tfor j in range(idx + 1 , len(rep)):\n\t\t\t\trep[j] = '0'\n\t\n\t# print(rep)\n\tans = 0\n\tfor j in rep:\n\t\tx = ord(j) - ord('0')\n\t\tans = ans * 3 + x\n\tprint(ans)\n", "passed": true, "time": 0.14, "memory": 14124.0, "status": "done"}, {"code": "#started 20 minutes late !\n\n# print(len(str(3**36)))\narr=[]\nfor i in range(40):\n    arr.append(3**i)\n# print(arr)\n\nn=int(input())\nfor i in range(n):\n    sb=[0]*40\n    a=int(input())\n    x=a\n    xx=a\n    for j in range(39,-1,-1):\n        if(a-arr[j]>=0):\n            a-=arr[j]\n            sb[j]=1\n    # print(x-a,1)\n    x=x-a\n    # print(sb)\n    if(a==0):\n        print(x)\n        continue\n    for j in range(40):\n        if(sb[j]==0):\n            x=x+3**j\n        # if(x>xx):\n            break\n        else:\n            x=x-3**j\n    print(x)\n# print(3**8)\n", "passed": true, "time": 0.14, "memory": 14128.0, "status": "done"}, {"code": "import sys\ndef I():\n    return sys.stdin.readline().rstrip()\n\nN = 39\np = [ 3 ** i for i in range( N ) ]\n\nq = int( I() )\nfor _ in range( q ):\n    n = int( I() )\n    a = [ 0 ] * N\n    for i in range( N - 1, -1, -1 ):\n        d = n // p[ i ]\n        n -= d * p[ i ]\n        if d == 2:\n            j = i + 1\n            while a[ j ]:\n                a[ j ] = 0\n                j += 1\n            a[ j ] = 1\n            break\n        a[ i ] = d\n    n = 0\n    for i in range( N ):\n        if a[ i ]:\n            n += p[ i ]\n    print( n )\n", "passed": true, "time": 0.14, "memory": 14408.0, "status": "done"}, {"code": "# -*- coding: utf-8 -*-\n# @Author: apikdech\n# @Date:   22:07:23 22-10-2019\n# @Last Modified by:   apikdech\n# @Last Modified time: 22:15:02 22-10-2019\ndef to_string(n):\n\tres = ''\n\twhile(n):\n\t\tres = str(n%3) + res\n\t\tn //= 3\n\tres = list(res)\n\treturn res\n\ndef to_int(s):\n\tres = 0\n\tfor i in range(len(s)):\n\t\tres *= 3\n\t\tres += int(s[i])\n\treturn res\n\nq = int(input())\nfor _ in range(q):\n\tn = int(input())\n\ts = to_string(n)\n\tgood = False\n\twhile(not good):\n\t\tcnt = 0\n\t\tidx = 10000\n\t\tfor i in range(len(s)):\n\t\t\tif (s[i] == '2'):\n\t\t\t\tcnt += 1\n\t\t\t\tidx = min(idx, i)\n\t\tif (cnt == 0) : good = True\n\t\tif (not good):\n\t\t\tfor i in range(idx+1, len(s)):\n\t\t\t\ts[i] = '0'\n\t\t\tn = to_int(s)\n\t\t\tn += 3**(len(s) - idx - 1)\n\t\t\ts = to_string(n)\n\tprint(n)", "passed": true, "time": 0.14, "memory": 14128.0, "status": "done"}, {"code": "# for _ in range(int(input())):\n#     n=int(input())\n# print((3**38)//10**18)    \na=[3**i for i in range(39)]\nfor _ in range(int(input())):\n    n=int(input())\n    ans=0\n    for i in range(38,-1,-1):\n        if n-a[i]>=0:\n            n-=a[i]\n            ans+=a[i]\n        elif n-a[i]<0 and  (3**i - 1)//2 <n:\n            n-=a[i]\n            ans+=a[i]\n    print(ans)        \n        \n        \n\n", "passed": true, "time": 0.14, "memory": 14320.0, "status": "done"}, {"code": "T = int(input())\nwhile T>0:\n    T-=1\n    n=int(input())\n    ss = n\n    a=[]\n    while n>0:\n        a.append(n%3)\n        n=n//3\n    fd = -1\n    a.append(0)\n    p = len(a)\n    for i in range(p-1,-1,-1):\n        if a[i]==2:\n            fd = i\n            break\n    if fd ==-1:\n        print(ss)\n    else:\n        for i in range(fd,p):\n            if a[i]==0:\n                a[i]=1\n                for j in range(0,i):\n                    a[j]=0\n                break\n        ans,k=0,1\n        for i in range(0,p):\n            ans += a[i]*k\n            k*=3\n        print(ans)\n", "passed": true, "time": 0.14, "memory": 14244.0, "status": "done"}, {"code": "q = int(input())\n\n\ndef dec_to_base(N, base):\n    if not hasattr(dec_to_base, 'table'):\n        dec_to_base.table = '0123456789ABCDEF'\n    x, y = divmod(N, base)\n    return dec_to_base(x, base) + dec_to_base.table[y] if x else dec_to_base.table[y]\n\n\nfor i in range(q):\n    n = int(input())\n    s = list(str(dec_to_base(n, 3)))\n    balance = n\n    for i in range(len(s) - 1, -1, -1):\n        if s[i] == \"2\":\n            balance -= 3 ** (len(s) - i - 1)\n            s[i] = \"1\"\n    for i in range(len(s) - 1, -1, -1):\n        if balance >= n:\n            break\n        if s[i] == \"0\" and balance < n:\n            s[i] = \"1\"\n            balance += 3 ** (len(s) - i - 1)\n    while balance < n:\n        balance *= 3\n        s.append(\"0\")\n        if balance < n:\n            s[-1] = \"1\"\n            balance += 1\n        else:\n            break\n    for i in range(len(s)):\n        if balance - 3 ** (len(s) - i - 1) >= n:\n            balance -= 3 ** (len(s) - i - 1)\n            s[i] = '0'\n    print(int(''.join(s), 3))\n", "passed": true, "time": 0.14, "memory": 14280.0, "status": "done"}, {"code": "q = int(input())\nout = []\nfor i in range(q):\n    n = int(input())\n    mm = 1\n    sts = []\n    while mm < n:\n        sts.append(mm)\n        mm *= 3\n    sts.append(mm)\n    m = sum(sts)\n    for i in range(len(sts) - 1, -1, -1):\n        if m - sts[i] < n:\n            continue\n        else:\n            m -= sts[i]\n    out.append(str(m))\nprint('\\n'.join(out))", "passed": true, "time": 0.14, "memory": 14104.0, "status": "done"}, {"code": "for _ in range(int(input())):\n    n = int(input())\n    l = []\n    j = -1\n    while (n):\n        temp1 = n % 3\n        n = n // 3\n        if (temp1 == 2):\n            temp1 = 0\n            j = len(l)\n        l.append(temp1)\n    l.append(0)\n    # print(l, j)\n    if (j != -1):\n        for i in range(j):\n            l[i] = 0\n        l[j + 1] += 1\n        while (l[j + 1] == 2):\n            j = j + 1\n            l[j] = 0\n            l[j + 1] += 1\n    # print(l)\n    s = ''\n    for i in l[::-1]:\n        s += str(i)\n    print(int(s, 3))\n", "passed": true, "time": 0.14, "memory": 14264.0, "status": "done"}]