B. K-я красивая строка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для заданного целого числа $$$n$$$ ($$$n > 2$$$) выпишем все строки длины $$$n$$$, которые содержат в себе $$$n-2$$$ буквы 'a' и две буквы 'b', в лексикографическом (алфавитном) порядке.

Напомним, что строка $$$s$$$ длины $$$n$$$ лексикографически меньше строки $$$t$$$ длины $$$n$$$, если существует такое $$$i$$$ ($$$1 \le i \le n$$$), что $$$s_i < t_i$$$, а для всех $$$j$$$ ($$$1 \le j < i$$$) $$$s_j = t_j$$$. Лексикографическое сравнение строк реализовано при помощи оператора < в современных языках программирования.

Например, если $$$n=5$$$, то получатся следующие строки (их порядок важен):

  1. aaabb
  2. aabab
  3. aabba
  4. abaab
  5. ababa
  6. abbaa
  7. baaab
  8. baaba
  9. babaa
  10. bbaaa

Легко показать, что такой список строк будет содержать ровно $$$\frac{n \cdot (n-1)}{2}$$$ строк.

Вам задано $$$n$$$ ($$$n > 2$$$) и $$$k$$$ ($$$1 \le k \le \frac{n \cdot (n-1)}{2}$$$). Выведите $$$k$$$-ю строку из списка.

Входные данные

Входные данные содержат один или несколько наборов тестовых данных.

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов тестовых данных в тесте. Затем следуют $$$t$$$ наборов тестовых данных.

Каждый набор тестовых данных содержится на отдельной строке, содержащей два целых числа $$$n$$$ и $$$k$$$ ($$$3 \le n \le 10^5, 1 \le k \le \min(2\cdot10^9, \frac{n \cdot (n-1)}{2})$$$.

Сумма значений $$$n$$$ по всем наборам тестовых данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора тестовых данных выведите $$$k$$$-ю строку из списка всех описанных выше строк длины $$$n$$$. Строки в списке отсортированы лексикографически (в алфавитном порядке).

Пример
Входные данные
7
5 1
5 2
5 8
5 10
3 1
3 2
20 100
Выходные данные
aaabb
aabab
baaba
bbaaa
abb
bab
aaaaabaaaaabaaaaaaaa