CF1328B K-th Beautiful String

给定一个整数 $n$（$n > 2$），我们要写出所有长度为 $n$ 的字符串，这些字符串包含 $n-2$ 个字母 'a' 和两个字母 'b'，并按照字典序（字母序）排列。 回忆一下，长度为 $n$ 的字符串 $s$ 若满足存在某个 $i$（$1 \le i \le n$），使得 $s_i < t_i$，并且对于任意 $j$（$1 \le j < i$）都有 $s_j = t_j$，那么字符串 $s$ 在字典序上小于字符串 $t$。现代编程语言中的字符串比较操作符 < 就是实现的字典序比较。 例如，如果 $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 \cdot 10^9, \frac{n \cdot (n-1)}{2})$）。 所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出长度为 $n$ 的字符串，即上述列表中第 $k$ 个字符串。字符串按字典序排列。

由 ChatGPT 4.1 翻译