# Power Strings

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 A

^{M}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