Sherlock, Mycroft and Watson are stuck in a closed room designed by his sister Eurus. And... suddenly water taps starts running and room is being filled with water. Being the loving sister(:D) that she is, Eurus presents Sherlock with a question. Its solution(s) will stop water taps and open the door of that room.
Help Sherlock save Watson before he dies in front of his eyes, well Watson is the shorter one and he would die first. The question is..
Given a string S with N characters , check for each of its prefix string P if it can be represented in the form n=1 Π n=k Xn for largest K > 1 (if there is one), for some string X where X is a non-periodic string. (A string w is periodic if there exists a string v such that w = vn = vv · · · v (n times), for some n ≥ 2. Note that in this case the length of v is strictly less than that of w. For example, aabaab is periodic, because it is vv for v = aab.). If yes then we want to know the length of prefix and value of K.
Note: output should be in the increasing order of the length of prefix.
CONSTRAINTS
2<=N<=100000
2<=K<10000
1<=X<=50
1<=T<=10
INPUT
First line of input file contains no. of testcases T. For each testcase input file contains two lines. The first one contains N the size of the string S. The second line contains the string S.
OUTPUT
For each testcase, for each prefix of length i that can be represented in the form n=1 Π n=k Xn and has K > 1, output the prefix size i and the period K separated by a single space on each line; the prefix sizes must be in increasing order.
Give a line space after output for each testcase.
for testcase 1:
prefix ‘aaa’ can be written as n=1 Π n=2 (a)n i.e. aaa. here X=a, length of prefix is 3
prefix ‘aaabaaabaaab’ can be written as n=1 Π n=2 (aaab)n i.e. aaabaaabaaab. here X=aaab, length of prefix is 12
for testcase 2:
prefix ‘ababab’ can be written as n=1 Π n=2 (ab)n i.e. ababab. here X=ab, length of prefix is 6
prefix ‘abababababab’ can be written as n=1 Π n=3 (ab)n i.e. abababababab. here X=ab, length of prefix is 12
Note: We did not considered prefix 'abababababab' as n=1 Π n=2 (abab)n
because abab is a periodic string i.e abab.
