题目描述

小 Y 给了小 X 一个长度为 $n$ 的只包含大写字母 $\tt{A,B,C}$ 的字符串。你可以对这个字符串进行如下操作：将子串 $\tt{ABC}$ 变成 $\tt{BCA}$。 小 X 想知道这个字符串最多能进行多少次操作。 一个字符串的子串是把这个字符串通过删去头部和尾部若干个字符形成的字符串。例如：$\tt{A,B,BB,AB,ABB}$ 是 $\tt{ABB}$ 的子串，$\tt{ABA}$ 不是 $\tt{ABBA}$ 的子串。

输入格式

一行一个长度为 $n$ 的字符串 $S$。

输出格式

一行一个整数表示答案。

ABCABC

3

ABCACCBABCBCAABCB

6

数据范围

对于全部测试点$: n \le 2×10^5$。

对于测试点 $1 \sim 4$ $: n \le 10$

对于测试点 $5 \sim 7$ $: n \le 1000$，并且保证无论按照什么顺序操作，被操作的子串两两不相交（换句话说，一个下标不会被两个被操作的字符串同时覆盖）

对于测试点 $8 \sim 10$ $: n \le 2×10^5$