PERIOD  Period
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.
Input
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.
Output
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.
Example
Input: 2 3 aaa 12 aabaabaabaab Output: Test case #1 2 2 3 3 Test case #2 2 2 6 2 9 3 12 4
hide comments
onlyerror:
20221006 12:03:08
Solve this problem first


rupok_03:
20200709 02:38:49
can someone explain me about test case 1??


fardin_abir:
20191031 07:11:28
just, failure function :P 

whoisshihab:
20170613 19:56:42
Can someone help me understand test case #1?


ankur_dhir95:
20170101 11:04:36
tricky one!!


kira28:
20161218 13:49:34
KMP Failure function!!!


Ajay Aneja:
20160727 15:07:19
In test case 2 aabaabaabaab


Shashank Tiwari:
20160103 04:03:39
In case you are confused about new lines , here is how you have to print :


xxbloodysantaxx:
20151211 09:33:52
Take Care of "c" in Test Case it isn't capital 

Sudharsansai:
20151020 15:29:30
Learnt a new thing..Never use "ios_base::sync_with_stdio(0)" in spoj . :P 
Added by:  ThanhVy Hua 
Date:  20041226 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  ACM South Eastern European Region 2004 