시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 12 7 7 58.333%

문제

아스키 코드가 97이상 126이하인 N개의 문자로 이루어진 문자열 S가 주어진다. 문자열 S의 모든 접두사에 대해, 각각의 접두사가 주기적인 문자열인지 아닌지 알고 싶다. 다시 말해 2 ≤ i ≤ N을 만족하는 각각의 i에 대해, 길이가 i인 문자열 S의 접두사가 어떤 문자열 A에 대해 A형태로 표현할 수 있는 가장 큰 K > 1을 알아내려 한다. 

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 줄로 이루어진다. 테스트 케이스의 첫 번째 줄에는 문자열 S의 길이인 정수 N이 주어진다 (2 <= N <= 1 000 000). 테스트 케이스의 두 번재 줄에는 문자열 S가 주어진다. 입력의 끝은 0으로 주어진다.

출력

각 테스트 케이스에 대해, "Test case #"과 테스트 케이스의 번호를 한 줄에 출력한다. 그 후, 길이가 i인 접두사의 주기가 K > 1인 경우, 접두사의 길이 i와 주기 K를 공백으로 분리하여 한 줄에 출력한다. 이 때, 접두사의 길이가 오름차순이 되도록 출력하여야 한다. 각 테스트 케이스에 대한 답을 출력한 후, 빈 줄을 한 줄 출력하여야 한다. 

예제 입력

3
aaa
12
aabaabaabaab
0

예제 출력

Test case #1
2 2
3 3

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

힌트