시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 19 9 9 64.286%

문제

아스키 코드가 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를 공백으로 분리하여 한 줄에 출력한다. 이 때, 접두사의 길이가 오름차순이 되도록 출력하여야 한다. 각 테스트 케이스에 대한 답을 출력한 후, 빈 줄을 한 줄 출력하여야 한다. 

예제 입력 1

3
aaa
12
aabaabaabaab
0

예제 출력 1

Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4
W3sicHJvYmxlbV9pZCI6IjM3NzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4ZmNcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzU0NFx1YzJhNFx1ZDBhNCBcdWNmNTRcdWI0ZGNcdWFjMDAgOTdcdWM3NzRcdWMwYzEgMTI2XHVjNzc0XHVkNTU4XHVjNzc4IE5cdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjQgU1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzVmNCBTXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM4MTFcdWI0NTBcdWMwYWNcdWM1ZDAgXHViMzAwXHVkNTc0LCZuYnNwO1x1YWMwMVx1YWMwMVx1Yzc1OCBcdWM4MTFcdWI0NTBcdWMwYWNcdWFjMDAgXHVjOGZjXHVhZTMwXHVjODAxXHVjNzc4Jm5ic3A7XHViYjM4XHVjNzkwXHVjNWY0XHVjNzc4XHVjOWMwIFx1YzU0NFx1YjJjY1x1YzljMCBcdWM1NGNcdWFjZTAgXHVjMmY2XHViMmU0LiBcdWIyZTRcdWMyZGMgXHViOWQwXHVkNTc0Jm5ic3A7MiZuYnNwOyZsZTsgaSAmbGU7IE5cdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCZuYnNwO2lcdWM1ZDAgXHViMzAwXHVkNTc0LCZuYnNwO1x1YWUzOFx1Yzc3NFx1YWMwMCBpXHVjNzc4IFx1YmIzOFx1Yzc5MFx1YzVmNCBTXHVjNzU4IFx1YzgxMVx1YjQ1MFx1YzBhY1x1YWMwMCBcdWM1YjRcdWI1YTQmbmJzcDtcdWJiMzhcdWM3OTBcdWM1ZjQmbmJzcDtBXHVjNWQwIFx1YjMwMFx1ZDU3NCBBPHN1cD5LJm5ic3A7PFwvc3VwPlx1ZDYxNVx1ZDBkY1x1Yjg1YyZuYnNwO1x1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0Jm5ic3A7XHVhYzAwXHVjN2E1IFx1ZDA3MCBLJm5ic3A7Jmd0OyZuYnNwOzFcdWM3NDQgXHVjNTRjXHVjNTQ0XHViMGI0XHViODI0IFx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwO1x1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjQ1MCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNCBTXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc3OCBcdWM4MTVcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQmbmJzcDsoMiAmbHQ7PSBOICZsdDs9IDEgMDAwIDAwMCkuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViNDUwIFx1YmM4OFx1YzdhYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0IFNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHViMDVkXHVjNzQwIDBcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCwgJnF1b3Q7VGVzdCBjYXNlICMmcXVvdDtcdWFjZmMgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWRmOCBcdWQ2YzQsIFx1YWUzOFx1Yzc3NFx1YWMwMCBpXHVjNzc4IFx1YzgxMVx1YjQ1MFx1YzBhY1x1Yzc1OCBcdWM4ZmNcdWFlMzBcdWFjMDAgSyZuYnNwOyZndDsmbmJzcDsxXHVjNzc4IFx1YWNiZFx1YzZiMCwgXHVjODExXHViNDUwXHVjMGFjXHVjNzU4IFx1YWUzOFx1Yzc3NCBpXHVjNjQwIFx1YzhmY1x1YWUzMCBLXHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWJkODRcdWI5YWNcdWQ1NThcdWM1ZWMgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YzgxMVx1YjQ1MFx1YzBhY1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzc0IFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWNkOWNcdWI4MjVcdWQ1NThcdWM1ZWNcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1YyBcdWQ2YzQsIFx1YmU0OCBcdWM5MDRcdWM3NDQgXHVkNTVjIFx1YzkwNCZuYnNwO1x1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzVlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzc3OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBlcmlvZCIsImRlc2NyaXB0aW9uIjoiPHA+Rm9yIGVhY2ggcHJlZml4IG9mIGEgZ2l2ZW4gc3RyaW5nIFMgd2l0aCBOIGNoYXJhY3RlcnMgKGVhY2ggY2hhcmFjdGVyIGhhcyBhbiBBU0NJSSBjb2RlIGJldHdlZW4gOTcgYW5kIDEyNiwgaW5jbHVzaXZlKSwgd2Ugd2FudCB0byBrbm93IHdoZXRoZXIgdGhlIHByZWZpeCBpcyBhIHBlcmlvZGljIHN0cmluZy4gVGhhdCBpcywgZm9yIGVhY2ggaSAoMiAmbGU7IGkgJmxlOyBOKSB3ZSB3YW50IHRvIGtub3cgdGhlIGxhcmdlc3QgSyAmZ3Q7IDEgKGlmIHRoZXJlIGlzIG9uZSkgc3VjaCB0aGF0IHRoZSBwcmVmaXggb2YgUyB3aXRoIGxlbmd0aCBpIGNhbiBiZSB3cml0dGVuIGFzIEE8c3VwPks8XC9zdXA+LCB0aGF0IGlzIEEgY29uY2F0ZW5hdGVkIEsgdGltZXMsIGZvciBzb21lIHN0cmluZyBBLiBPZiBjb3Vyc2UsIHdlIGFsc28gd2FudCB0byBrbm93IHRoZSBwZXJpb2QgSy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBmaWxlIGNvbnNpc3RzIG9mIHNldmVyYWwgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgdHdvIGxpbmVzLiBUaGUgZmlyc3Qgb25lIGNvbnRhaW5zIE4gKDIgJmx0Oz0gTiAmbHQ7PSAxIDAwMCAwMDApICZuZGFzaDsgdGhlIHNpemUgb2YgdGhlIHN0cmluZyBTLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgdGhlIHN0cmluZyBTLiBUaGUgaW5wdXQgZmlsZSBlbmRzIHdpdGggYSBsaW5lLCBoYXZpbmcgdGhlIG51bWJlciB6ZXJvIG9uIGl0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0ICZsZHF1bztUZXN0IGNhc2UgIyZyZHF1bzsgYW5kIHRoZSBjb25zZWN1dGl2ZSB0ZXN0IGNhc2UgbnVtYmVyIG9uIGEgc2luZ2xlIGxpbmU7IHRoZW4sIGZvciBlYWNoIHByZWZpeCB3aXRoIGxlbmd0aCBpIHRoYXQgaGFzIGEgcGVyaW9kIEsgJmd0OyAxLCBvdXRwdXQgdGhlIHByZWZpeCBzaXplIGkgYW5kIHRoZSBwZXJpb2QgSyBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2U7IHRoZSBwcmVmaXggc2l6ZXMgbXVzdCBiZSBpbiBpbmNyZWFzaW5nIG9yZGVyLiBQcmludCBhIGJsYW5rIGxpbmUgYWZ0ZXIgZWFjaCB0ZXN0IGNhc2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d