주기

아스키 코드 값이 $97$ 이상 $126$ 이하인 문자 $N$개로 이루어진 문자열 $S$가 주어진다. 문자열 $S$의 모든 접두사에 대해, 그 접두사가 주기적인 문자열인지 판별하려고 한다.

구체적으로, $2 \le i \le N$인 각 $i$에 대해 길이가 $i$인 $S$의 접두사를 생각하자. 이 접두사를 어떤 문자열 $A$를 $K$번 이어 붙인 형태 $A^K$로 나타낼 수 있는 가장 큰 $K > 1$을 구하려 한다.

여기서 $A^K$는 문자열 $A$를 $K$번 연속으로 이어 붙여 만든 문자열을 뜻한다. 예를 들어 $A$가 abad이고 $K = 3$이면 $A^K$는 abadabadabad이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 줄로 구성된다. 첫 번째 줄에는 문자열 $S$의 길이를 나타내는 정수 $N$이 주어진다 ($2 \le N \le 10^6$). 두 번째 줄에는 문자열 $S$가 주어진다. 입력의 끝은 $0$ 하나만 있는 줄로 나타낸다.

각 테스트 케이스마다 Test case #에 이어 테스트 케이스 번호를 붙여 한 줄에 출력한다. 그 후, 길이가 $i$인 접두사를 $A^K$ 꼴로 나타낼 수 있는 가장 큰 $K$가 $K > 1$인 경우, 접두사의 길이 $i$와 그 값 $K$를 공백으로 구분하여 한 줄에 출력한다. 이때 접두사의 길이 $i$가 오름차순이 되도록 출력한다. 각 테스트 케이스의 답을 출력한 뒤에는 빈 줄을 한 줄 출력한다.