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.
There are $T (1 <= T <= 100)$ test cases in this problem.
For every test cases,the first line has two integers $N (1 <= N <= 100)$, $K (1 <= K <= 6)$respectively representing the number of turns, the number of people.
The next $N$ rows with a char $c h$ and an integer $x (1 <= x <= 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).
For every test case, output the answer in a line.
## Input
There are $T (1 <= T <= 100)$ test cases in this problem.For every test cases,the first line has two integers $N (1 <= N <= 100)$, $K (1 <= K <= 6)$respectively representing the number of turns, the number of people.The next $N$ rows with a char $c h$ and an integer $x (1 <= x <= 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.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case, let $ n \in \mathbb{Z} $ be the initial number.
Let $ D(n) = \{ d \in \mathbb{Z} \mid 1 < d < n \text{ and } d \mid n \} $ be the set of positive proper divisors of $ n $.
**Constraints**
1. $ 1 \leq T \leq 10^3 $
2. $ 1 \leq n \leq 10^5 $
**Objective**
For each $ n $, determine the outcome of the impartial game where players alternately select a proper divisor of the previous move, starting with Chino. The player unable to move wins.
Define the game state by $ n $. A position is a *winning position* if the current player can force a win.
Let $ f(n) $ be:
- $ 0 $ if Chino wins immediately (i.e., $ D(n) = \emptyset $),
- $ -1 $ if Chino cannot win no matter the move (i.e., all moves lead to a winning position for David),
- $ \max D(n) $ if Chino can win by choosing the largest proper divisor that leads to a losing position for David.
Compute $ f(n) $ for each $ n $.