[CERC2014] Bricks

题目描述 给你一个由'B'和'W'组成的序列，将其按分成最多的区间且每个区间的'B':'W'的值相等 输入输出格式 输入格式： 多组数据，第一行一个整数T表示数据组数 每组数据的第一行为一个整数n，接下来n行，每行一个整数k和一个字符（'B'或'W'）表示在上一个序列后有一个长度为k的'B'或'W'的序列，序列的总长度不超过10^9 输出格式： 共T行，每行一个整数表示能分成的最多的区间数

You are given a sequence of white $(W)$ and black $(B)$ bricks. The goal is to partition it into some number of non-empty, 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 its 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.

The first line of input contains the number of test cases $T$. The descriptions of the test cases follow: Each test case starts with one line containing an integer $n(1 \le n \le 10^5)$ which is the length of the description of a sequence. Each of the following $n$ lines consists of an integer $k(1 \le k \le 10^9)$ 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^9$.

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

3
3
1 B
3 W
2 B
4
3 W
3 B
9 W
1 B
2
2 W
3 W

2
3
5