Little P 和 Little B 喜欢玩游戏，他们找到了 Little Skip。Little Skip 向他们介绍了以下游戏：

• 有一个包含小写字母的字符串 $S$，游戏开始时由 Skip 给定一个字符串 $S_0$。游戏记录 Little P 和 Little B 的得分，初始得分均为 0。
• Little P 和 Little B 轮流对该字符串进行操作，Little P 先手。每位玩家在自己的回合可以执行以下操作：
  • 选择 $S$ 的一个非空前缀（可以是 $S$ 本身），获得等于该前缀在 $S$ 中出现次数的得分，然后从 $S$ 中移除该前缀。
• 如果某次操作后 $S$ 变为空，游戏结束。

为了帮助你更好地理解游戏规则，请考虑以下示例：

• 初始时，$S_0 = \text{ababa}$；
• Little P 选择 $\text{ababa}$ 的前缀 $\text{a}$，获得 3 分，$S$ 变为 $\text{baba}$；
• Little B 选择 $\text{baba}$ 的前缀 $\text{ba}$，获得 2 分，$S$ 变为 $\text{ba}$；
• Little P 选择 $\text{ba}$，获得 1 分，字符串变为空，游戏结束。最终，Little P 获得 4 分，Little B 获得 2 分。

Little P 旨在最大化 Little P 的得分减去 Little B 的得分，而 Little B 旨在最小化该值。他们想知道，假设双方都极其聪明，Little P 的得分减去 Little B 的得分最终会是多少。

输入格式

输入的第一行包含一个由小写字母组成的字符串 $S_0$。保证 $1 \le |S_0| \le 10^6$。

输出格式

输出一行，包含一个整数，表示在双方都极其聪明的前提下，游戏结束时 Little P 与 Little B 的得分差。

样例

样例输入 1

ababa

样例输出 1

2

样例输入 2

letitrotwillwinworldfinals

样例输出 2

4