W&B

【题目背景】

在此键入。

【题目描述】

有一串由黑(B)白(W)两种颜色的方块构成的序列。你的目标就是将这串序列分成几部分，使得每一部分中两种颜色的方块的数目之比都相等。当然，一串序列总是可以只被分成一部分。下面给出两个例子：

* BWWWBB → BW + WWBB (ratio 1:1)

* WWWBBBWWWWWWWWWB → WWWB + BBWWWWWW + WWWB (ratio 3:1)

现在给出一个序列，如何将它分成尽可能多的部分呢？

【输入格式】

第一行包含一个正整数T，表示共有T组测试数据。

对于每一组测试数据，第一行包含一个正整数N。

接下来N行描述一个序列。每行包含一个正整数K和一个大写字母C，表示序列接下来有连续K个颜色为C的方块。

【输出格式】

对于每一组测试数据，输出一行，包含一个正整数，表示给出的序列最多能分成的部分的个数。

【样例输入】

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

【样例说明】

在此键入。

【数据规模与约定】

对于10%的数据，N ≤ 15；

对于20%的数据，N ≤ 500；

另有30%的数据，K = 1；

另有30%的数据，K ≤ 50；

对于100%的数据，N ≤ 10^5，序列长度不超过10^9。

保证对于全部测试点，输入文件行数不超过250*10^4。

【来源】

在此键入。