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