A. Playf and ABC
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Playf has a string $$$S$$$ with length $$$n$$$, which only contains three types of letters A, B, and C. She wants to find some triples $$$(i, j, k)$$$ where $$$0 \le i \lt j \lt k \lt n$$$, such that $$$\overline{S_iS_jS_k}=ABC$$$ or $$$\overline{S_iS_jS_k}= CBA$$$. But Playf does not want each character to be used repeatedly, so the index of each character appears in at most one triple.

Playf wants to know how many triples she can find at most, please help her.

Input

The first line contains a string $$$S (1\le |S| \le 3\times 10^5)$$$.

Output

Print an integer, the maximum number of triples Playf can find.

Examples
Input
ABCBBAC
Output
2
Input
ABCBBACCA
Output
2
Input
BACABA
Output
1
Note

For the first example, two triples are (0,1,6) and (2,3,5). There might be other set of two triples, but Playf can not find more than 2 triples in this example.