Bricks

You are given a sequence of white (W) and black (B) bricks. The goal is to partition it into some number of nonempty, contiguous blocks, each one having the same ratio of white and black bricks.

Of course, one can always “partition” the sequence into one single block (which is not very interesting). We want, however, to have as many blocks as possible. Consider, for example, the following sequences and their partitions:

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

Note that both of these partitions are optimal with respect to the number of blocks.

Input Specification

The first line of the input contains the number of test cases T. The descriptions of the test cases follow:

Each test case starts with a line containing an integer n (1 ≤ n ≤ 10⁵), which is the length of the description of a sequence. Each of the following n lines consists of an integer k (1 ≤ k ≤ 10⁹) and one of the characters W or B, meaning that k bricks of the given color follow next in the sequence. It is guaranteed that the total length of the brick sequence does not exceed 10⁹.

Output Specification

For each test case, output a single line containing the largest possible number of blocks.

Sample Input

1. 3
2. 3
3. 1 B
4. 3 W
5. 2 B
6. 4
7. 3 W
8. 3 B
9. 9 W
10. 1 B
11. 2
12. 2 W
13. 3 W

download as text file

Output for Sample Input

1. 2
2. 3
3. 5

download as text file

Original Problem

Central Europe Regional Contest, 2014