给定一个由白色（W）和黑色（B）砖块组成的序列。目标是将该序列划分为若干个非空的连续块，使得每个块中白色砖块与黑色砖块的数量比例相同。

当然，总是可以将序列“划分”为一个单独的块（这并不有趣）。然而，我们希望块的数量尽可能多。例如，考虑以下序列及其划分： BWWWBB = BW + WWBB（比例 1:1）， WWWBBBWWWWWWWWWB = WWWB + BBWWWWWW + WWWB（比例 3:1）。 注意，这两个划分在块的数量上都是最优的。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各测试用例的描述： 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示序列描述的长度。接下来的 $n$ 行，每行包含一个整数 $k$ ($1 \le k \le 10^9$) 和一个字符 W 或 B，表示序列中接下来有 $k$ 个对应颜色的砖块。保证输入文件的大小不超过 50.0 MiB，且 $\sum n \le 1.2 \times 10^7$。

输出格式

对于每个测试用例，输出一行，包含可能的最大块数。

样例

样例输入 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