薮猫喜欢脑力和他的脑力问题。
Serval 定义字符串 $$$T$$$ 是强大的,当且仅当 $$$T$$$ 可以通过多次连接某个字符串 $$$T'$$$ 来获得。正式地说,$$$T$$$ 是强大的,当且仅当存在一个字符串 $$$T'$$$ 和一个整数 $$$k\geq 2$$$ 使得 $$$$$$T=\underbrace{T'+T'+\dots+T'}_{k\text{ times}}$$$$$$
比如gogogo很强大,因为它可以通过连接3次go得到,但威力并不强大。
Serval 有一个由小写英文字母组成的字符串 $$$S$$$。他对 $$$S$$$ 的最长强大子序列感到好奇,他只需要你找出它的长度。如果 $$$S$$$ 的所有非空子序列都不强大,则答案被认为是 $$$0$$$。
如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)字符从 $$$b$$$ 获得,则字符串 $$$a$$$ 是字符串 $$$b$$$ 的子序列。
输入
第一行包含一个由小写英文字母组成的字符串 $$$S$$$ ($$$|S|\leq 80$$$)。
输出
打印单个整数 — $$$S$$$ 的最长有效子序列的长度。如果 $$$S$$$ 的所有非空子序列都不强大,则打印 $$$0$$$。
示例
输入 #1
buaa
输出 #1
2
输入 #2
codeforcesround
输出 #2
6
输入 #3
oooooooooooaaaaeaaiaujooooooooooooo
输出 #3
24
输入#4
zero
输出#4
0
注意
对于第一个样本,buaa 的所有非空子序列如下:
- b
- 你
- a(出现两次,buaa和buaa)
- 布
- ba(出现两次,buaa 和 buaa)
- ua(出现两次,buaa 和 buaa)
- AA
- bua (出现两次, buaa 和 buaa )
- 咩
- uaa
- buaa
由于 $$$\texttt{aa} = \texttt{a} + \texttt{a}$$$,aa 是一个强大的子序列。可以证明aa是其中唯一强大的子序列。所以答案是$$$2$$$。
对于第二个样本,最长的强大子序列是来自 codeforcesround 的 cocoded。所以答案是$$$6$$$。