我们最优秀的探险家 Vingying 在一个深洞中发现了满地的钻石！不过，他是一个非常谨慎的人，因此他决定在收集这些钻石之前先做一些研究。

这些钻石可以分为三种，为了方便起见，记为 A、B、C。总共有 $n$ 颗钻石排成一排，可以看作是一个从左到右的序列 $s_1, s_2, \dots, s_n$。Vingying 将会进行多次操作，每次操作按顺序包含以下三个步骤：

1. 选择一个满足 $s_i = \text{A}, s_{i+1} = \text{B}, s_{i+2} = \text{C}$ 的下标 $i$ ($1 \le i \le n - 2$)。
2. 如果下标 $i$ 是奇数，则收集 $s_i$ 和 $s_{i+2}$；否则，收集 $s_{i+1}$。
3. 将 $n$ 更新为剩余钻石的数量，并对剩余的钻石重新编号。

例如，若 $s = \text{ABCABC}$，我们可以选择下标 $1$ 并收集第 $1$ 和第 $3$ 颗钻石，此时 $s$ 变为 $\text{BABC}$，编号为 $1, 2, 3, 4$。但如果我们选择下标 $4$ 并收集第 $5$ 颗钻石，则 $s$ 变为 $\text{ABCAC}$，编号为 $1, 2, 3, 4, 5$。

Vingying 想知道他最多能进行多少次操作（不是收集钻石的数量）。

输入格式

输入包含一个仅由 A、B、C 组成的字符串，表示钻石的序列。字符串的长度不超过 $2 \times 10^5$。

输出格式

输出一个整数，表示最大操作次数。

样例

输入 1

ABCAAABCCC

输出 1

2

输入 2

AABCAAABCCC

输出 2

4