Periodic Prefixes

Let (X)^n denote the string made by writing string X consecutively n times. Thus (ab)^3 is ababab.

A string Y is periodic if it can be represented as (X)^n for some string X and some integer n > 1. The string ab is not periodic, but abab is periodic because it can be written as (ab)^2.

You are given a string S consisting only of lowercase English letters. For every prefix of S with length i, determine whether that prefix is periodic. If a prefix has more than one valid representation, choose the representation with the largest repetition count n.

Write a program that outputs every possible pair (i, n).

Constraints:

• 2 <= |S| <= 1,000,000
• S consists only of lowercase English letters.

The first line contains the string S.

In increasing order of i, output i and the maximum repetition count n for each qualifying prefix, one pair per line.