Lengths and Periods

In mathematics and computer science, the critical exponent of a string describes the largest number of times its contiguous substring is repeated in a row. The trick is that it can be a fraction. For example, the critical exponent of “Mississippi” is 7/3, as it contains the substring “ississi”, which is of length 7 and period 3.

The formal definition is as follows. Let w and x be non-empty strings. x is said to occur in w with exponent α, for positive rational α, if there is a substring y in w such as y = xnx0 where xn is x repeated n times, x0 is a prefix of x, n is the integer part of α, and the length |y| is equal to α|x|. The critical exponent of w is the maximum α over all xα that occur in w.

Given a string w, find its critical exponent.

The only line contains a string w — a sequence of lowercase English letters (1 ≤ |w| ≤ 200 000).

Output the critical exponent of w as an irreducible fraction p/q where p and q are integers without leading zeroes.