给定一个由字符 A、B 和 C 组成的字符串。该字符串中 A、B 和 C 的数量相等。

如果一个字符串满足以下条件，则称其为“优美字符串”： 其长度能被 3 整除。 该字符串可以被均匀地分割成若干个长度为 3 的连续子串，且每个子串都恰好包含一个 A、一个 B 和一个 C（顺序不限）。

例如：ABCCBA 是一个优美字符串，而 ABCAB 和 CCBAAB 则不是。

给定一个字符串，你需要将其划分为若干个子序列（不一定连续），使得每个子序列都是一个优美字符串。

例如，对于字符串 ABACBCAACCBB，我们可以进行如下划分： AB CA C B ACB A C B 这将其划分为了两个子序列 ABCACB 和 ACBACB，它们都是优美字符串。

对于给定的字符串，求出将其划分为优美字符串子序列所需的最少子序列数量。可以证明，对于所有满足输入约束的输入，至少存在一种这样的划分方式。

输入格式

输入的第一行包含一个字符串 $s$ ($3 \le |s| \le 3 \cdot 10^5$)。$|s|$ 能被 3 整除。$s$ 中包含相等数量的字符 A、B 和 C。

输出格式

输出一个整数，表示将 $s$ 划分为优美字符串子序列所需的最少子序列数量。

样例

样例输入 1

ABACBCAACCBB

样例输出 1

2