1005. 摩卡数

题目描述

小摩卡是个天才，尤其在字符串理论方面有着异于常人的天赋。为了赞颂她的才华，人们常常将那些满足特定优美性质的字符串命名为“摩卡串”。小摩卡上本科时，在数据结构与算法分析课程中学到了 KMP 自动机，并想出了如下构建一个字符串 S 的 KMP 自动机的算法。在算法中：

• S 是长度为 n 的输入字符串，仅包含前 σ 个小写字母。

• π 是 S 的前缀函数。π[i] 的值是满足 k < i 且 S[1, k] = S[i −k + 1, i] 的最大 k。若不存在这样的正整数 k，则 π[i] = 0。

• S[l, r] 表示仅保留 S 中第 l 个到第 r 个位置的字符所构成的子串。

• δ 是 KMP 自动机的转移表。δ[i, j] 表示如果当前状态为 i 且输入字符为 j，则新状态变为 δ[i, j]。

• k 是一个计数器。

小摩卡定义，算法结束后 k 的值即为字符串 S 的摩卡数。请你构造一个字符串 S 并指定 S 的字符集大小 σ，使得对字符串 S 运行该算

法，所得到的摩卡数恰好为 k。你需要保证构造的字符串的长度不超过 105。

输入格式

第一行输入一个正整数 T (1 ≤ T ≤ 50)，表示数据组数。接下来按如下格式输入 T 组数据：输入一行一个正整数 k (1 ≤ k ≤ 109 )，表示摩卡数的值。

输出格式

对于每组数据，输出两行：

• 第一行输出两个用空格分隔的正整数 n, σ，表示字符串的长度和字符集的大小。

• 第二行输出一行一个字符串 S。

你需要保证 1 ≤ n ≤ 105, 1 ≤ σ ≤ 26，S 的长度为 n，且 S 仅包含前 σ 个小写英文字母。本题使用 Special Judge 测试，如有多个满足条件的答案，你可以输出任意一种。你不需要最小化字符串 S 的长度或字典序。可以证明在题目限制内，一定存在至少一组满足条件的解。

样例输入

2
14
697

样例输出

6 3
abcabc
21 26
cbababcbbabcbbabcbabc

提示

请注意样例输出仅表示一种可能的合法答案，并不表示该样例输出恰好对应标准程序的输出。本题输出量可能较大，建议使用较快速的输出方式（如关闭流同步的cout）。

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第1场）