你得到一个由白色 (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$ 个该颜色的砖块。保证砖块序列的总长度不超过 $10^9$。

输出格式

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

样例

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