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 starts with the no. of test cases T.
Each test case contains a single string S in a separate line.
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.
Problem Setter:- Nitish Agarwal