Cho xâu \(S\) chỉ chứa ký tự \(A\) và \(B\). Tại mỗi bước đi, bạn phải chọn ra \(2\) hoặc \(3\) ký tự liên tiếp, sau đó đảo ngược lại (\(A\) thành \(B\), \(B\) thành \(A\)).

Yêu cầu: Hỏi cần tối thiểu bao nhiêu bước để tất cả ký tự trong xâu \(S\) đều giống nhau.

Input

• Một dòng duy nhất chứa xâu \(S\)

Output

• Số bước ít nhất để biến đổi xâu \(S\)

Điều kiện

• \(1 \le |S| \le 20\)

Sample Input 1

AABBBAA

Sample Output 1

1