题目描述

题目译自 Open Olympiad in Informatics 2018 Day2 T4 「Культурный контакт / Culture Contact」。

在 18 世纪初，一群欧洲探险家抵达了一个岛屿，岛上居住着从未与欧洲文明接触过的部落群体。

为了成功与土著建立联系，探险队队长计划向每个遇到的部落酋长赠送礼物。为此，他带来了一条由玻璃碎片组成的长链，这些玻璃碎片看起来像珍贵的宝石。我们将这条链子表示为一个字符串 $s$，由小写英文字母组成，每个字母表示链子上对应位置的玻璃碎片类型。探险家们打算将这条链子切割成若干片段，然后将每个片段赠送给一个部落酋长。队长决定按照以下规则分割链子：

• 为了不浪费过多时间进行切割，每个片段必须是链子上相邻的玻璃碎片组，即字符串 $s$ 的一个子串。
• 所有玻璃碎片都必须被使用，即每个玻璃碎片必须且仅被包含在一个片段中。
• 由于探险家们不知道土著如何评价不同类型的玻璃碎片，他们希望每个酋长收到的玻璃碎片集合（不考虑顺序）是相同的。换句话说，对于任何类型的玻璃碎片，每个片段中该类型的玻璃碎片数量必须相同。
• 探险家们不知道岛上有多少部落，因此准备的片段数量应尽可能多。

请帮助队长确定可以得到的最大片段数量。

输入格式

第一行包含一个非空字符串 $s$，由小写英文字母组成。字符串 $s$ 的长度不超过 $5 \cdot 10^6$ 个字符。

输出格式

输出一个整数，即探险家们可以将链子切割成的最多片段数量，且不违反队长制定的任何条件。

abbabbbab

3

在第一个样例中，探险家们可以将链子 abbabbbab 分割成片段 abb、abb 和 bab，这样每个遇到的部落酋长都会收到一个类型为 a 的玻璃碎片和两个类型为 b 的玻璃碎片。

aabb

1

在第二个样例中，无法将链子分割成超过一个片段，同时满足所有条件。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。