길이와 주기

수학과 컴퓨터 과학에서 문자열의 임계 지수(critical exponent)는 연속된 부분 문자열이 연달아 반복되는 횟수의 최댓값이다. 이 값은 분수가 될 수 있다. 예를 들어 "Mississippi"의 임계 지수는 $7/3$이다. 이 문자열에는 길이가 7이고 주기가 3인 부분 문자열 "ississi"가 들어 있기 때문이다. 공백이 아닌 문자열 $w$와 $x$를 생각한다. 양의 유리수 $\alpha$에 대해, $w$의 부분 문자열 $y$가 $y = x^n x_0$ 꼴로 존재하면 $x$는 지수 $\alpha$로 $w$에 나타난다고 한다. 여기서 $x^n$은 $x$를 $n$번 반복한 문자열, $x_0$는 $x$의 접두사, $n$은 $\alpha$의 정수 부분이며, $|y| = \alpha |x|$이다. $w$의 임계 지수는 $w$에 나타나는 모든 $x^\alpha$의 $\alpha$ 중 최댓값이다.

첫 줄에 영소문자로만 이루어진 문자열 $w$가 주어진다. 길이는 $1 \le |w| \le 200\,000$이다.

$w$의 임계 지수를 기약분수 $p/q$ 꼴로 출력한다. 여기서 $p$와 $q$는 앞에 0이 붙지 않는 정수이다.