You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

gza 在召唤！

题目描述

若一个字符串中的字符经过重新排列以后可以形成形如「$n$ 个 $\texttt{gza}$ 连接」的形式（除此之外无其他字符），则称该字符串价值为 $n$。如果字符串无法满足上述要求，那么这个字符串价值为 $0$。

如字符串 $\texttt{ggaazz}$ 价值为 $2$（可以重排为 $\texttt{gzagza}$，是两个 $\texttt{gza}$ 相连，除此之外没有其他字符），而字符串 $\texttt{gzagzb}$ 价值为 $0$。

给定一个字符串 $s$，求其所有非空子串价值的最大值。

非空子串的定义：使用 $s_i$ 表示 $s$ 中的第 $i$ 个字符（$1 \leq i \leq n$）。任取两个整数 $i, j$（$1 \leq i \leq j \leq n$），将 $s_i, s_{i + 1}, \cdots, s_{j}$ 截取出来顺次排列作为一个新的字符串，则这个字符串叫做 $s$ 的非空子串。
例如，当 $s = \texttt{abcde}$ 时，$\texttt{ab}, \texttt{bcde}, \texttt{c}, \texttt{abcde}$ 都是 $s$ 的非空子串，而 $\texttt{acd}, \texttt{f}, \texttt{ngioasd}, \texttt{" "}$ 都不是 $s$ 的非空子串。

输入格式

一行一个字符串，表示 $s$，含义见题面。

输出格式

一行一个整数，表示答案。

样例 #1

样例输入 #1

ggaza

样例输出 #1

1

样例 #2

样例输入 #2

ggzzaa

样例输出 #2

2

样例 #3

样例输入 #3

dawn

样例输出 #3

0

样例 #4

样例输入 #4

见下发文件中 ex_gza04.in。

样例输出 #4

见下发文件中 ex_gza04.out。

提示

样例 1 解释

选取其中第二至第四个字符，构成子串 $\texttt{gaz}$，重新排列后可以构成 $\texttt{gza}$，价值为 $1$。容易发现不存在价值 $\geq 2$ 的子串。

数据规模与约定

使用 $|s|$ 表示字符串 $s$ 的长度，对于 $100\%$ 的数据，$1 \le |s| \le 1200$。字符串仅由小写字母组成。