你有一些需要通过电子邮件发送的小写字母字符串，但其中一些字符串太长，直接输入会很麻烦。由于你发现了其中的重复部分，你决定尝试一种简单的压缩方法，即将重复的序列括在括号中，并在前面加上表示重复次数的数字。例如，字符串 “abababaaaaa” 可以表示为 “3(ab)5(a)” 或 “a3(ba)4(a)”。压缩表示的语法如下面的巴科斯范式（Backus-Naur form）所示，起始符号为 $S$。
$$ ::= $$
$$ )$$
$$
请注意，重复次数由单个数字指定，因此最多为 9 次，但可以通过嵌套来指定更多的重复次数。例如，三十个 “a” 可以表示为 “6(5(a))” 或 “3(5(2(a)))”。
请找出该压缩方案下给定字符串的最短表示。
输入格式
输入为一行，包含一个由小写字母组成的字符串。字符串的长度至少为 1，最多为 200。
输出格式
输出一行，包含输入字符串的最短可能表示。如果存在两个或多个最短表示，则输出其中任意一个即可。
样例
样例输入 1
abababaaaaa
样例输出 1
3(ab)5(a)
样例输入 2
abababcaaaaaabababcaaaaa
样例输出 2
2(3(ab)c5(a))
样例输入 3
abcdefg
样例输出 3
abcdefg