题目描述：

描述

对于给定的一个有 $N$ 个字符的字符串 $S$（每个字符的 ASCII 码值在 $97$ 到 $126$ 之间，包含 $97$ 和 $126$）的每一个前缀，我们想知道该前缀是否为一个周期字符串。也就是说，对于每一个 $i$($2 \leq i \leq N$)，我们想知道最大的($K > 1$)（如果存在的话），使得长度为 $i$ 的 $S$ 的前缀能够写成 $A^K$ 的形式，即对于某个字符串 $A$，$A$ 连接 $K$ 次的结果。当然，我们也想知道这个周期K的值。

输入：

输入由若干个测试用例组成。每个测试用例包含两行内容。第一行包含一个整数 $N$($2 \leq N \leq 1000000$)，表示字符串 $S$ 的长度。第二行包含字符串 $S$。输入文件以单独一行且该行上只有数字 $0$ 作为结束标志。

输出：

对于每个测试用例，在单独的一行上输出 "Test case #" 以及连续的测试用例编号；然后，对于每一个长度为 $i$ 且周期($K > 1$)的前缀，输出前缀的长度 $i$ 和周期 $K$，两者之间用单个空格隔开；前缀的长度必须按升序排列。在每个测试用例输出之后打印一个空行。

输入数据1

3
aaa
12
aabaabaabaab
0

输出数据1

Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4

来源：

2004 年东南欧