Period

You are given a string $S$ made of $N$ characters whose ASCII codes are between $97$ and $126$ inclusive. For every prefix of $S$, you want to decide whether that prefix is a periodic string.

More precisely, for each $i$ with $2 \le i \le N$, consider the prefix of $S$ of length $i$. You want the largest $K > 1$ such that this prefix can be written as $A^K$ for some string $A$.

Here $A^K$ denotes the string formed by concatenating $A$ exactly $K$ times. For example, if $A$ is abad and $K = 3$, then $A^K$ is abadabadabad.

The input consists of several test cases. Each test case is given on two lines. The first line contains an integer $N$, the length of the string $S$ ($2 \le N \le 10^6$). The second line contains the string $S$. The end of the input is indicated by a line containing a single $0$.

For each test case, print Test case # followed by the test case number on one line. Then, for every length $i$ whose prefix can be written as $A^K$ with a largest exponent $K > 1$, print the length $i$ and that value $K$ on one line, separated by a space. Print these lines in increasing order of the prefix length $i$. After the answer for each test case, print one blank line.