在数学和计算机科学中，一个字符串的临界指数（critical exponent）描述了其连续子串连续重复的最大次数。特别的是，这个次数可以是一个分数。例如，“Mississippi” 的临界指数是 $7/3$，因为它包含子串 “ississi”，该子串的长度为 $7$，周期为 $3$。

正式定义如下：设 $w$ 和 $x$ 是非空字符串。对于正有理数 $\alpha$，如果 $w$ 中存在一个子串 $y$，满足 $y = x^n x_0$，其中 $x^n$ 表示 $x$ 重复 $n$ 次，$x_0$ 是 $x$ 的前缀，$n$ 是 $\alpha$ 的整数部分，且长度 $|y|$ 等于 $\alpha |x|$，则称 $x$ 以指数 $\alpha$ 出现于 $w$ 中。$w$ 的临界指数是所有在 $w$ 中出现的 $x^\alpha$ 中 $\alpha$ 的最大值。

给定一个字符串 $w$，求其临界指数。

输入格式

唯一的一行包含一个字符串 $w$ —— 由小写英文字母组成的序列（$1 \le |w| \le 200\,000$）。

输出格式

输出 $w$ 的临界指数，表示为最简分数 $p/q$ 的形式，其中 $p$ 和 $q$ 是不含前导零的整数。

样例

输入样例 1

mississippi

输出样例 1

7/3

输入样例 2

abab

输出样例 2

2/1