#4045. [Cerc2014] bricks

内存限制:512 MiB 时间限制:20 Sec

题目描述

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'7 the sequence into one single block (which is not very 
interesting). We want, however, to have as manv blocks as possible. Consider for example the 
following sequences and its partitions: 
●BWWWBB 
BW + WWBB (rati0 1:1) 
~ WWWBBBWWWWWWWWWB 
WWWB + BBWWWWWW + WWWB (rati0 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《 n≤ 105) which is the length of 
the description of a sequence. Each of the following n lines consists of an integer k (1≤ k < 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 
Example

样例

样例输入


			
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

数据范围与提示