Our best explorer, Vingying, finds a deep cave that is full of diamonds! Well, he is a very careful man, so he decides to do some research before collecting them.

The diamonds can be divided into three kinds, noted as $$$\text{A,B,C}$$$ for convenience. There are a total of $$$n$$$ diamonds in a row, which can be regarded as a sequence $$$s_1,s_2,\dots,s_n$$$ from left to right. Vingying will perform the operation several times, which consists of the following three steps in order.

1. Choose an index $$$i$$$ ($$$1\le i \le n - 2$$$) satisfying $$$s_i = \text{A}$$$, $$$s_{i+1}=\text{B}$$$, $$$s_{i+2}=\text{C}$$$.
2. If the index is odd, then collect $$$s_i$$$ and $$$s_{i+2}$$$; otherwise, collect $$$s_{i+1}$$$.
3. Update $$$n$$$ to the number of diamonds left and reindex the diamonds.

For example, $$$s=\text{ABCABC}$$$. We can choose index $$$1$$$ and collect $$$1,3$$$, then $$$s$$$ becomes $$$\text{BABC}$$$ indexed $$$1,2,3,4$$$. But if we choose index $$$4$$$ and collect $$$5$$$, then $$$s$$$ becomes $$$\text{ABCAC}$$$ indexed $$$1,2,3,4,5$$$.

Vingying wants to know the maximum number of operations (not the diamonds) he can do.