Цеглини#7725
У вас є послідовність, що складається з білих (W) і чорних (B) цеглин. Потрібно розділити цю послідовність на непорожні блоки так, щоб у кожному з них співвідношення білих і чорних цеглин було однаковим.
Завжди можна розбити послідовність на один блок (але це нецікаво). Ми прагнемо отримати максимальну кількість блоків. Розгляньмо такі приклади послідовностей та їх розбиття:
• BWWWBB = BW + WWBB (співвідношення 1:1),
• WWWBBBWWWWWWWWWB = WWWB + BBWWWWWW + WWWB (співвідношення 3:1).
Обидва розбиття є оптимальними за кількістю блоків.
Перша строка містить кількість тестів .
Кожен тест починається з числа (1 \leq n \leq 10^5) — довжини опису послідовності. Кожен з наступних рядків містить число (1 \leq k \leq 10^9) і один з символів W або B, що визначають цеглин певного кольору в послідовності. Гарантується, що загальна довжина послідовності цеглин не перевищує 10^9.
Для кожного тесту виведіть в окремому рядку максимальну кількість блоків.
Приклад 1