Biến đổi xâu 'A'/'B' tối thiểu

Cho xâu ~S~ độ dài ~N~ chỉ gồm ký tự ~A~ và ~B~. Ta có hai phép biến đổi:

• (Op1) Thay ký tự ~S_i~ thành ký tự khác (~A \leftrightarrow B~).
• (Op2) Thay toàn bộ các ký tự từ ~S_1~ tới ~S_i~ thành ký tự khác (~A \leftrightarrow B~).

Hãy xác định số phép biến đổi ít nhất để đưa xâu ~S~ thành xâu gồm toàn ký tự ~A~.

Yêu cầu

Tính số bước tối thiểu để biến ~S~ thành ~AAA \ldots A~ khi được dùng hai phép biến đổi (Op1) và (Op2) bất kỳ số lần.

Dữ liệu

• Một dòng chứa xâu ~S~ chỉ gồm ~A~ và ~B~, với độ dài ~1 \le |S| \le 10^6~.

Kết quả

In ra một số nguyên là số phép biến đổi ít nhất.

Ví dụ

Ví dụ 1

Input

BBABBBBA

Output

2

Ví dụ 2

Input

AABBAA

Output

1

Giải thích

• Ví dụ 1: Một lời giải tối ưu là áp dụng (Op2) với ~i=7~ để lật tiền tố ~S_1..S_7~: ~BBABBBB\mathbf{A} \to AA\mathbf{B}A\mathbf{A}AA\mathbf{A}~, sau đó (Op1) lật ký tự ~S_3~ còn lại. Tổng cộng ~2~ bước.
• Ví dụ 2: Áp dụng (Op2) với ~i=4~: ~AABB\mathbf{AA} \to AAA\mathbf{AAA}~, đạt kết quả trong ~1~ bước.

Chấm điểm

100% số test thoả: $$ 1 \le |~S~| \le 10^6,\quad S \in \{A,B\}^{|S|}. $$