DreamGrid 刚刚在他的口袋里发现了一副麻将，其中包含 $3M$ 张花色牌和一张白板。每张花色牌都有一个花色（万、条或筒）和一个等级（从 $1$ 到 $M$），且每种等级和花色的组合恰好只有一张牌。

等级从 1 到 9 的万牌

等级从 1 到 9 的条牌

等级从 1 到 9 的筒牌

白板

由于 DreamGrid 感到无聊，他决定玩这些牌。他首先从 $3M$ 张花色牌中选出一张作为“幸运牌”，然后从这 $(3M + 1)$ 张牌中取出 $N$ 张，并按照以下规则对这 $N$ 张牌进行排序：

• 如果 $N$ 张牌中包含“幸运牌”，它必须被放置在最左侧。
• 对于两张都不是“幸运牌”的牌 $A$ 和 $B$，如果：
  • $A$ 是万牌，$B$ 是条牌，或者
  • $A$ 是万牌，$B$ 是筒牌，或者
  • $A$ 是条牌，$B$ 是筒牌，或者
  • $A$ 和 $B$ 花色相同且 $A$ 的等级小于 $B$ 的等级， 则 $A$ 必须放置在 $B$ 的左侧。

白板是一张特殊的牌。如果它包含在 $N$ 张牌中，在排序过程中，它被视为“幸运牌”的原始（非幸运）版本。例如，考虑以下已排序的牌，其中“3 万”被选为幸运牌。在这种情况下，白板被视为“3 万”的原始非幸运版本，应该放置在“2 万”和“4 万”之间。

由于 DreamGrid 非常健忘，他在排序后立刻忘记了哪张牌是幸运牌！给定 $N$ 张已排序的牌，请告诉 DreamGrid 可能的幸运牌数量。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $N$ 和 $M$ ($1 \le N, M \le 10^5, N \le 3M + 1$)，表示已排序的牌数和花色牌的最大等级。

接下来的 $N$ 行，第 $i$ 行描述从左到右第 $i$ 张已排序的牌。该行以一个大写字母 $s_i$ ($s_i \in \{C, B, D, W\}$) 开头，表示第 $i$ 张牌的花色：

• 如果 $s_i = C$，则后面跟一个整数 $r_i$ ($1 \le r_i \le M$)，表示这是一张等级为 $r_i$ 的万牌；
• 如果 $s_i = B$，则后面跟一个整数 $r_i$ ($1 \le r_i \le M$)，表示这是一张等级为 $r_i$ 的条牌；
• 如果 $s_i = D$，则后面跟一个整数 $r_i$ ($1 \le r_i \le M$)，表示这是一张等级为 $r_i$ 的筒牌；
• 如果 $s_i = W$，则表示这是一张白板。

保证至少存在一张可能的幸运牌，且所有测试数据的 $N$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示可能的幸运牌数量。

样例

输入 1

4
3 9
C 2
W
C 4
6 9
C 2
C 7
W
B 3
B 4
D 2
3 100
C 2
W
C 9
3 9
C 1
B 2
D 3

输出 1

2
4
7
25

说明

对于第一个样例，“2 万”和“3 万”是可能的幸运牌。

对于第二个样例，“8 万”、“9 万”、“1 条”和“2 条”是可能的幸运牌。