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 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

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

hide comments
2015-08-27 17:20:52
Take care of 'c' in 'case'.
nice question to solve.
2015-05-02 20:23:45 krish
KMP failure function that's all you need :)

Last edit: 2015-05-02 21:05:10
2015-04-26 20:27:18 Sunil
similar to findsr
2015-03-09 14:38:58 sai krishna
easy and good problem enjoyed kmp:)
2014-12-09 21:56:05 aqua
can anybody tell me why my code is giving run time error
<snip>

Last edit: 2023-01-19 16:55:13
2014-08-31 23:18:19 Hemanth Shivasubramaniam
I've tried numerous test cases, I seem to be getting the right output.
Why does it always say WA?
My code is here: <snip>

Last edit: 2023-01-19 16:55:18
2014-03-17 18:07:40 aristofanis
What is the proper way to read the input? scanf gets WA, while cin get AC...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.