题目描述

在数学和计算机科学中，字符串的 临界指数（critical exponent） 描述了某个连续子串可以连续重复的最大次数，而且这个次数可以是分数。

例如，字符串 mississippi 的临界指数为

因为其中包含子串 ississi，长度为 $7$，周期为 $3$。

形式化地，设 $w,x$ 为非空字符串。若 $w$ 中存在一个子串 $y$，满足

其中：

• $x^n$ 表示 $x$ 重复 $n$ 次；
• $x'$ 是 $x$ 的一个前缀；
• $n=\lfloor\alpha\rfloor$；
• $|y|=\alpha|x|$；

则称 $x$ 在 $w$ 中以指数 $\alpha$ 出现。

字符串 $w$ 的临界指数，是所有可能出现的指数 $\alpha$ 的最大值。

给定字符串 $w$，求它的临界指数。

输入格式

一行一个只包含小写英文字母的字符串 $w$：

输出格式

将临界指数以最简分数

的形式输出为：

p/q

其中 $p,q$ 均为无前导零整数，且 $\gcd(p,q)=1$。

样例

样例 1

mississippi

7/3

样例 2

abab

2/1