All Submissions


Given a string S of length N containing only lowercase letters. For each of the prefix we want to know whether the prefix is a power string or not. That is for each K (2<=K<=N) we want to know the largest M (M>1) such that the prefix of S with length K can be written as AM that is A concatenated M times, for some string A. We also want to know the power M.

INPUT

Input starts with the no. of test cases T.
Each test case contains a single string S in a separate line.

1<=T<=50
2<=N<=1,000,000

OUTPUT

For each test case output the following:-
For each prefix of length K having power M>1, output the prefix size K and the power M, separated by a single space.

Note:- The prefix sizes must be in increasing order. Print a blank line after each test case.



SAMPLE INPUT


2
bbbb
bbcbbcbbcbbc


SAMPLE OUTPUT


2 2
3 3
4 4

2 2
6 2
9 3
12 4


Problem Setter:- Nitish Agarwal

Languages: C,C++,Java

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0