题目背景

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）初赛。

题解等资源可在 https://gitlink.org.cn/thusaa/thupc2026pre 查看。

题目描述

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

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

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

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

输入格式

从标准输入读入数据。

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

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

输出格式

输出到标准输出。

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

3
2 1
2 676
3 16000

0
hi
1
gg
1
qwq

提示

【样例 1 解释】

·对于第一组测试数据，长为 $2$ 的字符串中，第 $1$ 小（即最小）的价值为 $0$，一个满足条件的字符串为 hi。当然，ab、yz 等字符串也满足条件。

·对于第二组测试数据，长为 $2$ 的字符串中，第 $676$ 小（即最大）的价值为 $1$，一个满足条件的字符串为 gg。当然，aa、zz 等字符串也满足条件。

·对于第三组测试数据，长为 $3$ 的字符串中，第 $16000$ 小的价值为 $1$ ，一个满足条件的字符串为 qwq。当然，cpp、lol 等字符串也满足条件。