K-th Beautiful String
Description
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.
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$.
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).
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).
Samples
7
5 1
5 2
5 8
5 10
3 1
3 2
20 100
aaabb
aabab
baaba
bbaaa
abb
bab
aaaaabaaaaabaaaaaaaa