p03018 AtCoder Grand Contest 034 - ABC
You are given a string s consisting of `A`, `B` and `C`.

Snuke wants to perform the following operation on s as many times as possible:

* Choose a contiguous substring of s that reads `ABC` and replace it with `BCA`.



Find the maximum possible number of operations.

Constraints

* 1 \leq |s| \leq 200000
* Each character of s is `A`, `B` and `C`.

Input

Input is given from Standard Input in the following format:


s


Output

Find the maximum possible number of operations.

Examples

Input

ABCABC


Output

3


Input

C


Output

0


Input

ABCACCBABCBCAABCB


Output

6
```python
S = input()
T = S.replace('BC','X')
res = 0
cnt = 0
for s in T:
    if s == 'A' :
        cnt += 1
    elif s == 'X':
        res += cnt
    else:
        cnt = 0
print(res)

```