#P4045. [Cerc2014] bricks
[Cerc2014] bricks
题目描述
一排砖块有白色(W)和黑色(B)两种。把整排砖划分成若干个非空连续段,使每段的白砖数与黑砖数之比相同,求最多能分成多少段。
如果一段的白砖、黑砖数分别为 ,两段比例相同指 。因此,若所有砖颜色相同,可以把每块砖单独分为一段。
输入格式
第一行输入数据组数 。每组先输入整数 ,表示压缩描述的行数。接下来 行,每行给出一个整数 和一个字母 W 或 B,表示在当前序列末尾接上 块这种颜色的砖。相邻两行可以描述同一种颜色。
输出格式
每组输出一行一个整数,表示最多能分成的段数。
样例 #1
样例输入 #1
3
3
1 B
3 W
2 B
4
3 W
3 B
9 W
1 B
2
2 W
3 W
样例输出 #1
2
3
5
数据范围
,,每组砖块总数不超过 。