Задана последовательность из белых (W) и черных (B) кирпичей. Следует разбить ее на такую непустую последовательность блоков, что в каждой из них отношение белых и черных кирпичей одинаково.

Всегда можно "разбить" последовательность на один блок (что нам не интересно). Мы хотим получить наибольшее количество блоков. Рассмотрим следующие последовательности и их разбиения:

• BWWWBB = BW + WWBB (отношение 1:1),

• WWWBBBWWWWWWWWWB = WWWB + BBWWWWWW + WWWB (отношение 3:1).

Оба разбиения оптимальны по отношению к числу блоков.

Входные данные

Первая строка содержит количество тестов t.

Каждый тест начинается числом n (1 ≤ n ≤ 105) - длиной последовательности. Каждая из следующих n строк содержит число k (1 ≤ k ≤ 109) и один из символов W или B, задающих k кирпичей определенного цвета в последовательности. Гарантируется, что общая длина последовательности кирпичей не превосходит 109.

Выходные данные

Для каждого теста вывести в отдельной строке искомое наибольшее количество блоков.