Basia 有一个字符串 $s$，其中每个字符都是英语字母表前 16 个小写字母中的一个。

该字符串中的每个字符都将被替换为向右或向上的箭头，但相同的字母必须被替换为相同的箭头。例如，字符串 “banan” 可以被替换为 $\uparrow\uparrow\rightarrow\uparrow\rightarrow$ 或 $\uparrow\uparrow\uparrow\uparrow\uparrow$，但你不能得到 $\rightarrow\rightarrow\rightarrow\uparrow\rightarrow$，因为这需要将两个字母 'a' 替换为不同的箭头。

Basia 将使用得到的箭头序列来绘制一条折线。她将从点 $(0, 0)$ 处的画笔开始，然后移动 $n$ 次，每次向右或向上移动 1 个单位——方向由下一个箭头决定。

我们将折线与 OX 轴之间的面积记为绘制的结果。形式上，该面积是满足 $y \ge 0$ 且存在一点 $(x, y')$ 属于该折线使得 $y' \ge y$ 的所有点 $(x, y)$ 的集合。

Basia 绘制出的最大可能面积是多少？

输入格式

标准输入的唯一一行包含一个字符串 $s$ ($1 \le |s| \le 300\,000$)，由英语字母表中的小写字母 'a'-'p'（共 16 种可能的字符）组成。

输出格式

输出一个整数，表示根据给定规则将字母转换为箭头后，绘制出的最大可能面积。

样例

输入 1

banan

输出 1

5

输入 2

abcdefghijklmnopaaaa

输出 2

90

说明

字符串 “banan” 应被替换为 $\uparrow\uparrow\rightarrow\uparrow\rightarrow$。此时折线下的面积为 5：

对于字符串 “abcdefghijklmnopaaaa”，有两种最优解，面积均为 90：