\(A, B, C\)로만 이루어졌고 길이가 \(|S|\)인 문자열 \(S\)가 있다. 당신은 이 문자열에 다음과 같은 시행을 할 수 있다.

• \(A\)와 그 뒤에 있는 \(B\)를 지운다. 
• \(B\)와 그 뒤에 있는 \(C\)를 지운다.

각 문자는 최대 한 번만 지울 수 있다.

예를 들어 \(ABCBA\)를 보자. 각 문자에 왼쪽부터 1번, 2번, 3번. . . 과 같이 번호를 붙이면 다음과 같이 시행할 수 있다.

• 1번 \(A\)와 2번 \(B\)를 지운다. 이 경우 시행의 횟수는 1번이고, 남은 문자열은 \(CBA\)이다. 어떤 두 문자를 골라도 시행의 조건을 만족시킬 수 없으므로, 더 이상 시행을 할 수 없다. 
• 1번 \(\A\)와 4번 \(B\)를 지우고, 이어 2번 \(B\)와 3번 \(C\)를 지운다. 이 경우 시행의 횟수는 2번이고 남은 문자열은 A이다. 문자열에남은 문자가 하나이므로, 더 이상 시행을 할 수 없다

이외에도 시행을 할 수 있는 여러 경우의 수가 있다.

시행을 할 수 있는 최대 횟수를 구해라.

첫 번째 줄에 문자열 \(S\)가 주어진다.

• \(1 \le |S| \le 300 000 \)
• \(S\)의 모든 문자는 \(A, B, C\) 중 하나이다.

1. (5점) \(S\)의 모든 문자는 \(A, B\) 중 하나이다. 
2. (20점) \(|S| ≤ 300. \)
3. (32점) \(|S| ≤ 1 000. \)
4. (43점) 추가 제약 조건 없음.