时间限制： 2.0 秒 空间限制： 512 MiB

题目描述

对于一个长为 \(n\) 的、仅由 a,b,...,z 构成的字符串 \(s\)，考虑一张含 \(n\) 个点的无向带权图，每两个点 \(i, j\)（\(i \ne j\)）间有权值为 \(LCP(suf_i, suf_j)\)\(^{\dagger}\) 的边，其中 \(suf_i = s[i:n]\)。

Ecrade_ 定义字符串 \(s\) 的价值为该图最大生成树的边权之和。

Ecrade_ 想要请你找出所有长为 \(n\) 的、仅由 a,b,...,z 构成的字符串中，价值第 \(k\) 小的任意一个。

\(^{\dagger}\) \(LCP(s_1, s_2)\) 定义为字符串 \(s_1\) 与 \(s_2\) 的最长公共前缀的长度。

输入格式

从标准输入读入数据。

第一行一个整数 \(T\)（\(1 \le T \le 2 \times 10^5\)），表示测试数据组数。

对于每组测试数据，一行两个整数 \(n, k\)（\(1 \le n\)，\(\sum n \le 4 \times 10^5\)，\(1 \le k \le \min(26^n, 10^{15})\)）。

输出格式

输出到标准输出。

对于每组测试数据，第一行输出第 \(k\) 小的价值，第二行输出一行一个长为 \(n\) 的、价值第 \(k\) 小的字符串。若有多个字符串满足条件，输出其中任意一个即可。

样例

样例 1 输入

3
2 1
2 676
3 16000

样例 1 输出

0
ab
1
aa
1
aab

样例 1 解释

• 对于第一组测试数据，长为 \(2\) 的字符串中，第 \(1\) 小（即最小）的价值为 \(0\)，一个满足条件的字符串为 hi。当然，ab、yz 等字符串也满足条件。
• 对于第二组测试数据，长为 \(2\) 的字符串中，第 \(676\) 小（即最大）的价值为 \(1\)，一个满足条件的字符串为 gg。当然，aa、zz 等字符串也满足条件。
• 对于第三组测试数据，长为 \(3\) 的字符串中，第 \(16000\) 小的价值为 \(1\)，一个满足条件的字符串为 qwq。当然，cpp、lol 等字符串也满足条件。