题目描述

给你一个只由 A、B、C 三种字符组成的字符串 $S$。

定义一次操作：选出三个下标 $i<j<k$，满足 $S_i=$ A、$S_j=$ B、$S_k=$ C，把这三个字符从 $S$ 中删掉，剩下的字符保持原来的顺序拼在一起。

求最多能进行多少次操作。

输入格式

一行，一个字符串 $S$。

输出格式

一行一个整数，表示最多的操作次数。

样例

ABACBCC

2

CBACBB

0

BBBAAABCBCBAACBBCAAC

5

数据范围与提示

样例 1 解释：先选 $(1,2,7)$，剩下 ACBC；再选 $(1,3,4)$，剩下 C。不能操作 3 次。

来源：AtCoder ABC447 D「Take ABC 2」。