For the given integer $n$ ($n > 2$) let's write down all the strings of length $n$ which contain $n-2$ letters 'a' and two letters 'b' in lexicographical (alphabetical) order.

Recall that the string $s$ of length $n$ is lexicographically less than string $t$ of length $n$, if there exists such $i$ ($1 \le i \le n$), that $s_i < t_i$, and for any $j$ ($1 \le j < i$) $s_j = t_j$. The lexicographic comparison of strings is implemented by the operator < in modern programming languages.

For example, if $n=5$ the strings are (the order does matter):  aaabb  aabab  aabba  abaab  ababa  abbaa  baaab  baaba  babaa  bbaaa 

It is easy to show that such a list of strings will contain exactly $\frac{n \cdot (n-1)}{2}$ strings.

You are given $n$ ($n > 2$) and $k$ ($1 \le k \le \frac{n \cdot (n-1)}{2}$). Print the $k$-th string from the list.


-----Input-----

The input contains one or more test cases.

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test. Then $t$ test cases follow.

Each test case is written on the the separate line containing two integers $n$ and $k$ ($3 \le n \le 10^5, 1 \le k \le \min(2\cdot10^9, \frac{n \cdot (n-1)}{2})$.

The sum of values $n$ over all test cases in the test doesn't exceed $10^5$.


-----Output-----

For each test case print the $k$-th string from the list of all described above strings of length $n$. Strings in the list are sorted lexicographically (alphabetically).


-----Example-----
Input
7
5 1
5 2
5 8
5 10
3 1
3 2
20 100

Output
aaabb
aabab
baaba
bbaaa
abb
bab
aaaaabaaaaabaaaaaaaa
[{"code": "#!usr/bin/env python3\nfrom collections import defaultdict, deque\nfrom heapq import heappush, heappop\nfrom itertools import permutations, accumulate\nimport sys\nimport math\nimport bisect\ndef LI(): return [int(x) for x in sys.stdin.readline().split()]\ndef I(): return int(sys.stdin.readline())\ndef LS():return [list(x) for x in sys.stdin.readline().split()]\ndef S():\n    res = list(sys.stdin.readline())\n    if res[-1] == \"\\n\":\n        return res[:-1]\n    return res\ndef IR(n):\n    return [I() for i in range(n)]\ndef LIR(n):\n    return [LI() for i in range(n)]\ndef SR(n):\n    return [S() for i in range(n)]\ndef LSR(n):\n    return [LS() for i in range(n)]\n\nsys.setrecursionlimit(1000000)\nmod = 1000000007\n\ndef solve():\n    t = I()\n    for _ in range(t):\n        n,k = LI()\n        f = 1\n        p = 1\n        while f <= k:\n            f += p\n            p += 1\n        f -= p\n        p -= 2\n        k -= f\n        p = n-p\n        k = n-k\n        ans = \"a\"*(p-2)+\"b\"+\"a\"*(k-p+1)+\"b\"+\"a\"*(n-k-1)\n        print(ans)\n    return\n\n#Solve\ndef __starting_point():\n    solve()\n\n__starting_point()", "passed": true, "time": 0.16, "memory": 14348.0, "status": "done"}, {"code": "t = int(input())\nfor i in range(t):\n    n, k = map(int, input().split())\n    fbp = n - 2\n    cur = 1\n    while cur < k:\n        k -= cur\n        fbp -= 1\n        cur += 1\n    sbp = n - k\n    cnt = 0\n    for j in range(n):\n        if j == fbp:\n            print('b', end='')\n        elif j == sbp:\n            print('b', end='')\n        else:\n            print('a', end='')\n    print()", "passed": true, "time": 0.14, "memory": 14344.0, "status": "done"}, {"code": "def calc(n, k):\n    k -= 1\n    a, b = 0, 1\n    for i in range(1, n + 2):\n        if k - i >= 0:\n            k -= i\n            b += 1\n        else:\n            break\n    a += k\n    return \"\".join([\"b\" if i == a or i == b else \"a\" for i in range(n)[::-1]])\n\nT = int(input())\nfor _ in range(T):\n    n, k = list(map(int, input().split()))\n    print(calc(n, k))\n", "passed": true, "time": 0.14, "memory": 14084.0, "status": "done"}, {"code": "for _ in range(int(input())):\n    n, k = map(int, input().split())\n    low = 1\n    high = n - 1\n    ans = n\n    while low <= high:\n        mid = (high+low)//2\n        temp = mid * ( mid + 1)//2\n        if temp >= k:\n            ans = min(ans, mid)\n            high = mid - 1\n        else:\n            low = mid + 1\n    temp = ans*(ans+1)//2 - k\n    result = ['a'] * n\n    result[n - ans - 1] = 'b'\n    result[n- ans + temp] = 'b'\n    print(''.join(result))", "passed": true, "time": 0.14, "memory": 14260.0, "status": "done"}, {"code": "for tc in range(int(input())):\n    size, pos = list(map(int, input().split()))\n    tl = 1\n    tot = 0\n    while tot + tl < pos:\n        tot += tl\n        tl += 1\n    res = ['a' for _ in range(size)]\n    res[-tl-1] = 'b'\n    res[-(pos-tot)] = 'b'\n    print(''.join(res))\n    \n", "passed": true, "time": 0.14, "memory": 14324.0, "status": "done"}, {"code": "t = int(input())\nfor case_num in range(t):\n    n, k = list(map(int, input().split(' ')))\n    l = 1\n    r = n - 1\n    while l <= r:\n        mid = (l + r) // 2\n        num = mid * (mid + 1) // 2\n        if k <= num:\n            r = mid - 1\n        else:\n            l = mid + 1\n    num = l * (l + 1) // 2\n    ans = ['a' for i in range(n)]\n    ans[-l-1] = 'b'\n    rest = l - num + k\n    ans[-rest] = 'b'\n    print(''.join(ans))\n", "passed": true, "time": 0.14, "memory": 14312.0, "status": "done"}, {"code": "def go():\n    n,k = map(int,input().split())\n    x=1\n    for i in range(n-2,-1,-1):\n        if k>n-1-i:\n            k-=n-1-i\n        else:\n            ans=['a']*n\n            ans[i]='b'\n            ans[n-k]='b'\n            return ''.join(ans)\n\n\n\n\n# x,s = map(int,input().split())\nt = int(input())\n# t=1\nans=[]\nfor _ in range(t):\n    # go()\n    ans.append(str(go()))\n\nprint('\\n'.join(ans))", "passed": true, "time": 0.14, "memory": 14220.0, "status": "done"}, {"code": "def solve():\n\tA = list(map(int,input().split()))\n\tp1 = A[0] -1\t\n\tp2 = A[0]\n\tfat = 1\n\t\n\tA[1] = A[1] -1\n\twhile A[1]>=fat:\n\t\tp1 = p1-1\n\t\tA[1] = A[1] - fat\n\t\tfat = fat + 1\n\t\t\n\t\n\tp2 = p2 - A[1]\n\tfor i in range(1,A[0]+1):\n\t\tif i==p1 or i==p2:\n\t\t\tprint('b',end='')\n\t\telse:\n\t\t\tprint('a',end='')\n\tprint('')\n\t\t\t\t\t\n\nT = int(input())\nfor i in range(T):\n\tsolve()\t", "passed": true, "time": 0.14, "memory": 14116.0, "status": "done"}, {"code": "import sys\ndef input():\n\treturn sys.stdin.readline()[:-1]\nt = int(input())\nfor _ in range(t):\n\tn, k = list(map(int, input().split()))\n\tcur, level, add = 0, 0, 1\n\tk -= 1\n\twhile k >= cur + add:\n\t\tcur += add\n\t\tlevel += 1\n\t\tadd += 1\n\tx, y = n-2-level, n-1-(k - cur)\n\tans = [\"a\" for _ in range(n)]\n\tans[x], ans[y] = \"b\", \"b\"\n\tprint(\"\".join(ans))\n", "passed": true, "time": 0.14, "memory": 14336.0, "status": "done"}, {"code": "t = int(input())\n\nfor _ in range(t):\n    n, k = list(map(int, input().split()))\n    \n    opts = 0\n    b_pos = n-2\n    while opts+(n-b_pos-1)<k:\n        opts += n-b_pos-1\n        b_pos -= 1\n        \n    b_pos2 = n - (k-opts)\n    \n    res = [\"a\"] * n\n    res[b_pos] = \"b\"\n    res[b_pos2] = \"b\"\n    print(\"\".join(res))\n        \n    \n", "passed": true, "time": 0.14, "memory": 14344.0, "status": "done"}, {"code": "t = int(input())\nfor iii in range(t):\n\tn, k = list(map(int, input().split()))\n\ti = 1\n\twhile k > i:\n\t\tk -= i\n\t\ti += 1\n\ts = [\"a\"] * n\n\ts[-i-1] = \"b\"\n\ts[-k] = \"b\"\n\tprint(\"\".join(map(str, s)))\n", "passed": true, "time": 0.14, "memory": 14104.0, "status": "done"}, {"code": "import math\nt = int(input())\nfor i in range(t):\n    n,k = list(map(int,input().split(\" \")))\n    k-=1 #zero-index\n    m = int((1+math.sqrt(1+8*k))/2)\n    tri = int(m*(m-1)/2)\n    s = k-tri\n    #print(m)\n    #print(s)\n    s = \"a\"*(n-m-1)+\"b\"+\"a\"*(m-s-1)+\"b\"+\"a\"*s\n    print(s)\n", "passed": true, "time": 0.14, "memory": 14120.0, "status": "done"}]