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

Difficulty: introductory

Starter code:

Solutions:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    t = I()
    for _ in range(t):
        n,k = LI()
        f = 1
        p = 1
        while f <= k:
            f += p
            p += 1
        f -= p
        p -= 2
        k -= f
        p = n-p
        k = n-k
        ans = "a"*(p-2)+"b"+"a"*(k-p+1)+"b"+"a"*(n-k-1)
        print(ans)
    return

#Solve
def __starting_point():
    solve()

__starting_point()

t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    fbp = n - 2
    cur = 1
    while cur < k:
        k -= cur
        fbp -= 1
        cur += 1
    sbp = n - k
    cnt = 0
    for j in range(n):
        if j == fbp:
            print('b', end='')
        elif j == sbp:
            print('b', end='')
        else:
            print('a', end='')
    print()

def calc(n, k):
    k -= 1
    a, b = 0, 1
    for i in range(1, n + 2):
        if k - i >= 0:
            k -= i
            b += 1
        else:
            break
    a += k
    return "".join(["b" if i == a or i == b else "a" for i in range(n)[::-1]])

T = int(input())
for _ in range(T):
    n, k = list(map(int, input().split()))
    print(calc(n, k))


for _ in range(int(input())):
    n, k = map(int, input().split())
    low = 1
    high = n - 1
    ans = n
    while low <= high:
        mid = (high+low)//2
        temp = mid * ( mid + 1)//2
        if temp >= k:
            ans = min(ans, mid)
            high = mid - 1
        else:
            low = mid + 1
    temp = ans*(ans+1)//2 - k
    result = ['a'] * n
    result[n - ans - 1] = 'b'
    result[n- ans + temp] = 'b'
    print(''.join(result))

for tc in range(int(input())):
    size, pos = list(map(int, input().split()))
    tl = 1
    tot = 0
    while tot + tl < pos:
        tot += tl
        tl += 1
    res = ['a' for _ in range(size)]
    res[-tl-1] = 'b'
    res[-(pos-tot)] = 'b'
    print(''.join(res))
    


t = int(input())
for case_num in range(t):
    n, k = list(map(int, input().split(' ')))
    l = 1
    r = n - 1
    while l <= r:
        mid = (l + r) // 2
        num = mid * (mid + 1) // 2
        if k <= num:
            r = mid - 1
        else:
            l = mid + 1
    num = l * (l + 1) // 2
    ans = ['a' for i in range(n)]
    ans[-l-1] = 'b'
    rest = l - num + k
    ans[-rest] = 'b'
    print(''.join(ans))


def go():
    n,k = map(int,input().split())
    x=1
    for i in range(n-2,-1,-1):
        if k>n-1-i:
            k-=n-1-i
        else:
            ans=['a']*n
            ans[i]='b'
            ans[n-k]='b'
            return ''.join(ans)




# x,s = map(int,input().split())
t = int(input())
# t=1
ans=[]
for _ in range(t):
    # go()
    ans.append(str(go()))

print('\n'.join(ans))

def solve():
	A = list(map(int,input().split()))
	p1 = A[0] -1	
	p2 = A[0]
	fat = 1
	
	A[1] = A[1] -1
	while A[1]>=fat:
		p1 = p1-1
		A[1] = A[1] - fat
		fat = fat + 1
		
	
	p2 = p2 - A[1]
	for i in range(1,A[0]+1):
		if i==p1 or i==p2:
			print('b',end='')
		else:
			print('a',end='')
	print('')
					

T = int(input())
for i in range(T):
	solve()	

import sys
def input():
	return sys.stdin.readline()[:-1]
t = int(input())
for _ in range(t):
	n, k = list(map(int, input().split()))
	cur, level, add = 0, 0, 1
	k -= 1
	while k >= cur + add:
		cur += add
		level += 1
		add += 1
	x, y = n-2-level, n-1-(k - cur)
	ans = ["a" for _ in range(n)]
	ans[x], ans[y] = "b", "b"
	print("".join(ans))


t = int(input())

for _ in range(t):
    n, k = list(map(int, input().split()))
    
    opts = 0
    b_pos = n-2
    while opts+(n-b_pos-1)<k:
        opts += n-b_pos-1
        b_pos -= 1
        
    b_pos2 = n - (k-opts)
    
    res = ["a"] * n
    res[b_pos] = "b"
    res[b_pos2] = "b"
    print("".join(res))
        
    


t = int(input())
for iii in range(t):
	n, k = list(map(int, input().split()))
	i = 1
	while k > i:
		k -= i
		i += 1
	s = ["a"] * n
	s[-i-1] = "b"
	s[-k] = "b"
	print("".join(map(str, s)))


import math
t = int(input())
for i in range(t):
    n,k = list(map(int,input().split(" ")))
    k-=1 #zero-index
    m = int((1+math.sqrt(1+8*k))/2)
    tri = int(m*(m-1)/2)
    s = k-tri
    #print(m)
    #print(s)
    s = "a"*(n-m-1)+"b"+"a"*(m-s-1)+"b"+"a"*s
    print(s)