Problem Description

Now there are $K$ people play Halli Galli game.They will play $N$ turns in all,in the order of the first player,the second player,$\cdots$,the $K$ player,the first player,$\cdots$.

In one turn,the player will display a card on his side,if there are $a$ kinds of fruit which its total ammount is exactly 5 in all sides,the bell will be pushed $a$ times in this turn.Notices that the previous card will be covered by the current card.

Now you have to calculate the total times they push the bell in $N$ turns.

Input

There are $T(1 \leq T \leq 100)$ test cases in this problem.

For every test cases,the first line has two integers $N(1 \leq N \leq 100)$, $K(1 \leq K \leq 6)$respectively representing the number of turns, the number of people.

The next $N$ rows with a char $ch$ and an integer $x(1 \leq x \leq 5)$,respectively representing the type of fruit on the card,the ammount of fruit on the card.

There are always four kinds of fruit,respectively $A$,$B$,$G$,$P$(Apple,Banana,Grape,Pear).

Output

For every test case, output the answer in a line.

1
5 3
A 5
B 2
B 3
G 1
P 5

6