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
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
Sunil: 2015-04-26 20:27:18

similar to findsr

sai krishna: 2015-03-09 14:38:58

easy and good problem enjoyed kmp:)

aqua: 2014-12-09 21:56:05

can anybody tell me why my code is giving run time error
http://ideone.com/dq07MI

Hemanth Shivasubramaniam: 2014-08-31 23:18:19

I've tried numerous test cases, I seem to be getting the right output.
Why does it always say WA?
My code is here: http://pastebin.com/FjGBB6XQ

Last edit: 2014-08-31 23:18:39
aristofanis: 2014-03-17 18:07:40

What is the proper way to read the input? scanf gets WA, while cin get AC...


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