
ZOJ Problem Set  4034
DreamGrid has just found a set of Mahjong with $3M$ suited tiles and a White Dragon tile in his pocket. Each suited tile has a suit (Character, Bamboo or Dot) and a rank (ranging from 1 to $M$), and there is exactly one tile of each rank and suit combination. Character tiles whose rank ranges from 1 to 9 Bamboo tiles whose rank ranges from 1 to 9 Dot tiles whose rank ranges from 1 to 9 White Dragon tile As DreamGrid is bored, he decides to play with these tiles. He first selects one of the $3M$ suited tiles as the "lucky tile", then he picks $N$ tiles from the set of $(3M+1)$ tiles and sorts these $N$ tiles with the following rules:
White Dragon tile is a special tile. If it's contained in the $N$ tiles, it's considered as the original (notlucky) version of the lucky tile during the sorting. For example, consider the following sorted tiles, where "3 Character" is selected as the lucky tile. White Dragon tile, in this case, is considered to be the original notlucky version of "3 Character" and should be placed between "2 Character" and "4 Character". As DreamGrid is quite forgetful, he immediately forgets what the lucky tile is after the sorting! Given $N$ sorted tiles, please tell DreamGrid the number of possible lucky tiles. InputThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains two integers $N$ and $M$ ($1 \le N, M \le 10^5$, $N \le 3M+1$), indicating the number of sorted tiles and the maximum rank of suited tiles. For the next $N$ lines, the $i$th line describes the $i$th sorted tile counting from left to right. The line begins with a capital letter $s_i$ ($s_i \in \{C, B, D, W\}$), indicating the suit of the $i$th tile:
It's guaranteed that there exists at least one possible lucky tile, and the sum of $N$ in all test cases doesn't exceed $10^6$. OutputFor each test case output one line containing one integer, indicating the number of possible lucky tiles. Sample Input4 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 Sample Output2 4 7 25 HintFor the first sample, "2 Character" and "3 Character" are possible lucky tiles. For the second sample, "8 Character", "9 Character", "1 Bamboo" and "2 Bamboo" are possible lucky tiles. Author: CHEN, Shihan Source: The 15th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple 