벽돌 분할

흰색(W) 벽돌과 검은색(B) 벽돌이 한 줄로 놓여 있다. 이 줄을 비어 있지 않은 연속된 블록 여러 개로 나누되, 모든 블록에서 흰 벽돌과 검은 벽돌의 비율이 같아야 한다. 블록 개수를 최대로 하는 것이 목표다.

줄 전체를 블록 하나로 두는 분할은 언제나 가능하지만 의미가 없다. 다음 두 분할을 보자.

• BWWWBB = BW + WWBB (비율 1:1)
• WWWBBBWWWWWWWWWB = WWWB + BBWWWWWW + WWWB (비율 3:1)

두 분할 모두 블록 개수 기준으로 최적이다.

한 가지 색만 놓인 줄에서는 어떻게 나누어도 모든 블록의 비율이 같으므로, 벽돌을 하나씩 떼어 낸 분할이 최대다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 100$).

각 테스트 케이스의 첫 줄에는 줄을 나타내는 구간의 개수 $n$이 주어진다 ($1 \le n \le 10^5$). 이어지는 $n$개의 줄에는 정수 $k$와 문자 W 또는 B가 하나씩 주어진다 ($1 \le k \le 10^9$). 이는 그 색의 벽돌 $k$개가 이어서 놓여 있다는 뜻이다. 같은 색이 연속한 구간으로 주어질 수도 있다. 한 테스트 케이스에서 벽돌 개수의 합은 $10^9$을 넘지 않고, 모든 테스트 케이스의 $n$ 합은 $10^5$을 넘지 않는다.

각 테스트 케이스마다 만들 수 있는 블록 개수의 최댓값을 한 줄에 출력한다.