奶牛贝西刚刚截获了农夫约翰发送给汉堡女王的短信!然而,贝西确信里面隐藏着秘密信息。
文本是小写拉丁字母的字符串$$$s$$$。如果 $$$t$$$ 作为索引形成算术级数的 $$$s$$$ 的子序列存在,她认为字符串 $$$t$$$ 隐藏在字符串 $$$s$$$ 中。例如,字符串 aab 隐藏在字符串 aaabb 中,因为它出现在索引 $$$1$$$、$$$3$$$ 和 $$$5$$$ 处,这些索引形成等差数列,公差为 $$$2$$$。贝西认为任何出现次数最多的隐藏字符串就是秘密消息。如果索引集不同,则 $$$S$$$ 子序列的两次出现是不同的。帮助她找出秘密信息出现的次数!
例如,字符串aaabb中,a被隐藏$$$3$$$次,b被隐藏$$$2$$$次,ab被隐藏$$$6$$$次,aa被隐藏$$$3$$$次,bb被隐藏$$$1$$$次,aab被隐藏$$$2$$$次,aaa被隐藏$$$1$$$次,abb被隐藏$$$1$$$ 次,aaab 被隐藏 $$$1$$$ 次,aabb 被隐藏 $$$1$$$ 次,aaabb 被隐藏 $$$1$$$ 次。秘密消息出现的次数为$$$6$$$。
输入
第一行包含一个由小写拉丁字母组成的字符串 $$$s$$$ ($$$1 \le |s| \le 10^5$$$) — Bessie 截获的文本。
输出
输出一个整数——秘密消息出现的次数。
示例
输入 #1
aaabb
输出 #1
6
输入 #2
usaco
输出 #2
1
输入 #3
lol
输出 #3
2
注意
在第一个示例中,这些是所有隐藏字符串及其索引集:
- a 出现在 $$$(1)$$$、$$$(2)$$$、$$$(3)$$$
- b 出现在 $$$(4)$$$、$$$(5)$$$
- ab 出现在 $$$(1,4)$$$、$$$(1,5)$$$、$$$(2,4)$$$、$$$(2,5)$$$、$$$(3,4)$$$、$$$(3,5)$$$
- aa 出现在 $$$(1,2)$$$、$$$(1,3)$$$、$$$(2,3)$$$
- bb 出现在 $$$(4,5)$$$
- aab 出现在 $$$(1,3,5)$$$, $$$(2,3,4)$$$
- aaa 出现在 $$$(1,2,3)$$$
- abb 出现在 $$$(3,4,5)$$$
- aaab 出现在 $$$(1,2,3,4)$$$
- aabb 出现在 $$$(2,3,4,5)$$$
- aaabb 出现在 $$$(1,2,3,4,5)$$$
在第二个示例中,隐藏字符串不会出现多次。
在第三个示例中,隐藏字符串是字母 l。