PERIOD - Period

no tags 

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 AK , 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
whoisshihab: 2017-06-13 19:56:42

Can someone help me understand test case #1?
Edit: Now I understand that.

Last edit: 2017-06-13 20:25:21
ankur_dhir95: 2017-01-01 11:04:36

tricky one!!

kira28: 2016-12-18 13:49:34

KMP Failure function!!!
XD XD

Ajay Aneja: 2016-07-27 15:07:19

In test case 2 aabaabaabaab
12 2 could be the output ?
as it can be aabaab aabaab

Shashank Tiwari: 2016-01-03 04:03:39

In case you are confused about new lines , here is how you have to print :

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

After 3 3 , Test case #2 begins on very next line. No problems.

xxbloodysantaxx: 2015-12-11 09:33:52

Take Care of "c" in Test Case it isn't capital

Sudharsansai: 2015-10-20 15:29:30

Learnt a new thing..Never use "ios_base::sync_with_stdio(0)" in spoj . :P

gaurav117: 2015-08-27 17:20:52

Take care of 'c' in 'case'.
nice question to solve.

shiva: 2015-05-12 00:30:52

Last edit: 2015-05-12 00:53:50
krish: 2015-05-02 20:23:45

KMP failure function that's all you need :)

Last edit: 2015-05-02 21:05:10

Added by:Thanh-Vy Hua
Date:2004-12-26
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