PERIOD - Period

如果一个字符串S是由一个字符串T重复K次形成的，则称T是S的循环元。使K最大的字符串T称为S的最小循环元，此时的K称为最大循环次数。 现给一个给定长度为N的字符串S，对S的每一个前缀S[1~i]，如果它的最大循环次数大于1，则输出该前缀的长度和最大循环次数。 感谢@super_kidding 提供的翻译

For each prefix of a given string **_S_** with **_N_** characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each **_i_** (2 <= **_i_** <= **_N_**) we want to know the largest **_K_** > 1 (if there is one) such that the prefix of **_S_** with length **_i_** can be written as **_A_ $ ^{K} $** , that is **_A_** concatenated **_K_** times, for some string **_A_**. Of course, we also want to know the period **_K_**.

The first line of the input file will contains only the number _T (1 <= T <= 10)_ of the test cases. Each test case consists of two lines. The first one contains **_N_** (2 <= **_N_** <= 1 000 000) – the size of the string **_S_**. The second line contains the string **_S_**.

For each test case, output “Test case #” and the consecutive test case number on a single line; then, for each prefix with length **i** that has a period **K** > 1, output the prefix size **i** and the period **K** separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case.

2
3
aaa
12
aabaabaabaab

Test case #1
2 2
3 3

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