Кирпичи
Задана последовательность из белых (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.
Выходные данные
Для каждого теста вывести в отдельной строке искомое наибольшее количество блоков.