J. Boboge and Card Shuffle
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Boboge 手上有一副牌，这副牌由 H ， Z ， C ， U 四种花色组成，每种花色的牌恰好 $$$n$$$ 张，编号 $$$1$$$ 到 $$$n$$$ ，一共 $$$4n$$$ 张。现在他想通过若干次操作，将这副牌重新洗牌，使得每种花色的牌形成的子序列其编号递增，且最后 $$$n$$$ 张牌的花色均为 U 。

一次操作中， Boboge 可以将一张牌抽出并重新插入任意位置（可以是任意两张牌之间，第一张牌前面或最后一张牌后面）。

问 Boboge 最少需要几次操作来洗牌？

一个序列的子序列指的是删去序列中任意个元素（可以一个不删，删去的元素不一定要连续），形成的新序列。

Input

输入第一行包含一个整数 $$$T\ (1 \le T \le 10^4)$$$ ，代表测试组数。

对于每组测试用例，第一行包含一个数 $$$n\ (1 \le n \le 10^5)$$$ ，代表每种花色牌的数量。

接下来一行由 $$$4n$$$ 个字符串组成，每个字符串代表一张牌，第一个字符为一个大写字母，代表花色，后面紧跟一个数字代表对应的编号。例如， H114 代表 H 花色编号为 $$$114$$$ 的牌。

确保 $$$\sum n\le{10^5}$$$ 。

Output

对于每组测试点，输出一个整数代表最少需要的操作次数。

Example
Input
3
2
H1 Z1 C1 C2 Z2 H2 U1 U2
2
H1 Z1 C1 U1 H2 Z2 C2 U2
10
C10 C2 Z3 H7 C8 Z7 U1 C3 C5 H10 U2 U4 Z6 H9 Z4 Z2 U3 H5 U8 Z5 H8 C7 C6 C4 Z9 U6 C1 H4 U5 Z8 H3 U9 H2 H1 U10 H6 Z1 Z10 C9 U7
Output
0
1
27
Note

需要注意的是，同种花色 ( U 除外) 不一定要排在相邻的位置，比如 H1 Z1 C1 H2 C2 Z2 U1 U2 是一种合法的排序方式。

题面样例中第3组测试用例有由于数据太长导致换行的情况，仅作展示作用，实际测试数据中无换行。