SP263 PERIOD - Period

如果一个字符串 $S$ 是由一个字符串 $T$ 重复 $K$ 次形成的，则称 $T$ 是 $S$ 的循环元。使 $K$ 最大的字符串 $T$ 称为 $S$ 的最小循环元，此时的 $K$ 称为最大循环次数。 现给一个给定长度为 $N$ 的字符串 $S$，对 $S$ 的每一个前缀 $S[1\sim i]$，如果它的最大循环次数大于 $1$，则输出该前缀的长度和最大循环次数。

第一行将仅包含测试用例的数量 $T (1 \le T \le 10)$。 每个测试用例包含两行。 第一行一个整数 $N (2 \le N \le 1\times 10^6)$ 表示字符串 $S$ 的长度，第二行一个字符串 $S$。

对于每个测试用例，第一行输出 `Test case #` 和测试点编号。接下来对于每个长度为 $i$ 且 $K > 1$ 的前缀，输出前缀大小 $i$ 和循环次数 $K$，前缀大小按递增顺序排列。在每个测试点后打印一个空白行。

Translate by [@qifan_maker](/user/706607).