Розворот ABC

Вхідні дані

У першому рядку задано одне ціле число $T$ (1\le T\le 10^5) — кількість наборів вхідних даних. Далі задано опис наборів вхідних даних.

У першому рядку кожного набору вхідних даних задано одне ціле число $n$ (1 \le n \le 10^6) — довжина рядка $s$.

У другому рядку кожного набору вхідних даних задано рядок $s$ довжини $n$, що складається з символів $\text{A}$, $\text{B}$ та $\text{C}$.

Гарантується, що сума $n$ по всім наборам вхідних даних одного тесту не перевищує 10^6.

Вихідні дані

Для кожного набору вхідних даних виведіть в окремому рядку одне ціле число — найбільшу кількість послідовних операцій, які можна виконати з рядком $s$.

Приклади

Примітка

У першому наборі вхідних даних першого прикладу можна виконати не більше ніж $3$ послідовні операції з рядком ABCCA. Одним з прикладів того, як $3$ послідовні операції можна виконати, є [ABCCA $\to$ BACCA, BACCA $\to$ BACAC, BACAC $\to$ BAACC].

Оцінювання

Нехай $K$ — сума $n$ по всім наборам вхідних даних одного тесту.

1. ($2$ бали): відповідь рівна $0$ або $1$;

2. ($3$ бали): n \le 3;

3. ($5$ балів): s_i \ne \texttt{C} для 1 \le i \le n;

4. ($5$ балів): $s$ має вигляд \texttt{AA}\ldots \texttt{AABB}\ldots \texttt{BBCC}\ldots \texttt{CC} (тобто x \cdot \texttt{A} + y \cdot \texttt{B} + z \cdot \texttt{C} для певних додатних $x$, $y$, $z$);

5. ($9$ балів): s_is_{i+1} \ne \texttt{CA} для 1 \le i < n;

6. ($10$ балів): T = 1, n \le 12;

7. ($8$ балів): n \le 12;

8. ($28$ балів): K \le 2000;

9. ($30$ балів): без додаткових обмежень.