题目描述

对于给定字符串 $S$ 的每个前缀，我们想知道它是否为周期串（周期串定义为由若干最小循环节拼接而成的字符串），若是，输出前缀长度和循环节数量。

输入格式

多组数据，每组数据第一行一个整数 $n$，表示字符串 $s$ 的长度，若 $n=0$ 则结束输入。

若 $n\ne0$，则第二行一个字符串 $S$，如题意。

输出格式

对于第 $i$ 组输出，第一行一个字符串 Test case #i。

之后若干行一行两个整数，表示如果字符串 $S$ 的一个前缀是周期串，它的长度和循环节数量（注意这里的循环节是指长度最小的循环节）。

之后再空一行。

样例输入

3
aaa
12
aabaabaabaab
0

样例输出

Test case #1
2 2
3 3

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

说明

$n\leq10^6$，字符串 $S$ 均由小写字母构成。

### 题目描述

对于给定字符串 $S$ 的每个前缀，我们想知道它是否为周期串（周期串定义为由若干最小循环节拼接而成的字符串），若是，输出前缀长度和循环节数量。

### 输入格式

多组数据，每组数据第一行一个整数 $n$，表示字符串 $s$ 的长度，若 $n=0$ 则结束输入。

若 $n\ne0$，则第二行一个字符串 $S$，如题意。

### 输出格式

对于第 $i$ 组输出，第一行一个字符串 `‘Test case #i`。

之后若干行一行两个整数，表示如果字符串 $S$ 的一个前缀是周期串，它的长度和循环节数量（注意这里的循环节是指**长度最小的**循环节）。

之后再空一行。

### 说明

$n\leq10^6$，字符串 $S$ 均由小写字母构成。

样例输入

3
aaa
12
aabaabaabaab
0

样例输出

Test case #1
2 2
3 3

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