Bricks

A row of white (W) and black (B) bricks is given. Split the row into non-empty contiguous blocks so that every block has the same ratio of white bricks to black bricks. Make the number of blocks as large as possible.

Keeping the whole row as one block is always possible and not interesting. Look at these two partitions.

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

Both are optimal in the number of blocks.

If the row holds one color only, every block has the same ratio no matter how you cut, so splitting the row into single bricks is optimal.

The first line contains the number of test cases $T$ ($1 \le T \le 100$).

Each test case starts with a line containing the number of runs $n$ that describe the row ($1 \le n \le 10^5$). Each of the next $n$ lines contains an integer $k$ and one of the characters W or B ($1 \le k \le 10^9$). This means that $k$ bricks of that color come next in the row. The same color can appear in consecutive runs. The total number of bricks in one test case does not exceed $10^9$, and the sum of $n$ over all test cases does not exceed $10^5$.

For each test case, print the largest possible number of blocks on its own line.