题目描述

如果一个字符串 $S$ 是由一个字符串 $T$ 重复 $K$ 次形成的，则称 $T$ 是 $S$ 的循环元。使 $K$ 最大的字符串 $T$ 称为 $S$ 的最小循环元，此时的 $K$ 称为最大循环次数。

现给一个给定长度为 $N$ 的字符串 $S$，对 $S$ 的每一个前缀 $S[1~i]$，如果它的最大循环次数大于 $1$，则输出该前缀的长度和最大循环次数。

输入格式

第一行一个整数 $T$，表示数据组数，$1 \le T \le 10$。

每组数据包含两行，第一行一个整数 $N$，第二行一个字符串 $S$，$2 \le N \le 10^6$。

输出格式

对于每组数据输出时以 Test case #k 开头，$k$ 表示测试数据组数，紧接着输出不超过 $N$ 行，每行两个整数表示前缀的长度和最大循环次数。

两组数据之间输出一个空行。

2
3
aaa
12
aabaabaabaab

Test case #1
2 2
3 3

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