Trong hội trại năm nay, Tí được lớp giao nhiệm vụ tham gia trò chơi giải mật thư tìm kho báu. Mật thư có ~n~ kí tự chỉ gồm hai loại kí tự là A và B. Trong mật thư, nếu số lần chuỗi con AA xuất hiện nhiều hơn số lần xuất hiện của chuỗi con BB thì đáp án của mật thư là số lần xuất hiện chuỗi con AA và ngược lại.

Tí vô tình làm ướt mật thư nên một số kí tự có thể bị nhòe mực, lúc này kí tự nhòe bị thay thế bởi kí tự *.

Yêu cầu: Hãy giúp Tí tìm ra một số lớn nhất có thể là đáp án của mật thư nếu nó không bị ướt.

INPUT

• Dòng đầu tiên chứa số nguyên dương ~n~ là độ dài của mật thư (~1 \leq n \leq 10^6~).
• Dòng thứ hai chứa n kí tự A, B hoặc * được ghi liền tiếp không chứa dấu cách.

OUTPUT

Chỉ gồm một số nguyên duy nhất là đáp án của bài toán.

SAMPLE INPUT 1

5
AABBB

SAMPLE OUTPUT 1

2

Giải thích:

• Chuỗi AA xuất hiện ~1~ lần. Chuỗi BB xuất hiện ~2~ lần. Vậy đáp án bài toán là ~2~.

SAMPLE INPUT 2

4 
A*BB

SAMPLE OUTPUT 2

2

Giải thích:

• Nếu kí tự * là kí tự B thì chuỗi BB xuất hiện ~2~ lần, còn chuỗi AA không xuất hiện lần nào.
• Ngược lại nếu kí tự * là kí tự A thì chuỗi AA xuất hiện ~1~ lần và chuỗi BB cũng xuất hiện ~1~ lần. Vậy đáp án bài toán là ~2~.

SUBTASKS

• ~50\%~ test tương ứng ~50\%~ số điểm với mật thư chỉ gồm hai kí tự A và B.
• ~50\%~ test tương ứng ~50\%~ số điểm còn lại không có ràng buộc gì thêm.