주기 접두사

문자열 X를 n번 이어 붙인 문자열을 (X)^n으로 나타낸다. 예를 들어 (ab)^3은 ababab이다.

어떤 문자열 Y가 (X)^n 꼴로 표현될 수 있고 n > 1이라면, Y를 주기적인 문자열이라고 한다. 예를 들어 ab는 주기적인 문자열이 아니지만, abab는 (ab)^2로 표현할 수 있으므로 주기적인 문자열이다.

알파벳 소문자로만 이루어진 문자열 S가 주어진다. S의 앞에서부터 i개의 문자로 이루어진 접두사가 주기적인 문자열이 되는 모든 경우를 찾아야 한다. 한 접두사를 여러 가지 방법으로 표현할 수 있다면, 반복 횟수 n이 가장 큰 표현을 선택한다.

가능한 모든 (i, n) 쌍을 구하는 프로그램을 작성하시오.

제한:

• 2 <= |S| <= 1,000,000
• S는 알파벳 소문자로만 이루어져 있다.

첫째 줄에 문자열 S가 주어진다.

i가 증가하는 순서대로, 조건을 만족하는 i와 그때의 최대 반복 횟수 n을 한 줄에 하나씩 출력한다.