题目描述

如果一个字符串 $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$，前缀大小按递增顺序排列。在每个测试点后打印一个空白行。

输入输出样例 #1

输入 #1

2
3
aaa
12
aabaabaabaab

输出 #1

Test case #1
2 2
3 3

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

说明/提示

Translate by @qifan_maker.