题目描述

给定一个长度为 $N$ 的字符串 $S$，其中 $2 \leq N \leq 10^6$。

定义 $P_i = S[1..i]$，即字符串 $S$ 的前 $i$ 个字符组成的前缀。对于某些 $P_i$，如果它可以表示为某个字符串重复 $K$ 次（$K > 1$ 且 $K$ 尽可能大）的形式，则输出对应的 $i$ 和 $K$。

输入格式

多组测试数据。

每组数据第一行包含一个整数，表示字符串的长度 $N$。第二行包含一个长度为 $N$ 的字符串 $S$。

输入以 $0$ 表示结束。

输出格式

对于每组测试数据，首先输出一行 Test case #X，其中 $X$ 表示当前是第几组测试数据（从 $1$ 开始编号）。然后按顺序输出所有满足条件的 $i$ 和 $K$，每对 $i$ 和 $K$ 占一行。

3
aaa
12
aabaabaabaab
0

Test case #1
2 2
3 3

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

解释：

• 对于第一组数据，字符串为 aaa：

  • 前缀 $P_2 = \text{"aa"}$ 可以表示为 $\text{"a"}$ 重复 $2$ 次；
  • 前缀 $P_3 = \text{"aaa"}$ 可以表示为 $\text{"a"}$ 重复 $3$ 次。

• 对于第二组数据，字符串为 aabaabaabaab：

  • 前缀 $P_2 = \text{"aa"}$ 可以表示为 $\text{"a"}$ 重复 $2$ 次；
  • 前缀 $P_6 = \text{"aabaab"}$ 可以表示为 $\text{"aab"}$ 重复 $2$ 次；
  • 前缀 $P_9 = \text{"aabaabaab"}$ 可以表示为 $\text{"aab"}$ 重复 $3$ 次；
  • 前缀 $P_{12} = \text{"aabaabaabaab"}$ 可以表示为 $\text{"aab"}$ 重复 $4$ 次。