Description

Niuniu has recently become obsessed with a card game called Dou Dizhu. Dou Dizhu is a poker game played with a deck of $54$ cards: $A$ through $K$ in Spades, Hearts, Clubs, and Diamonds, plus the two Jokers. In Dou Dizhu, the card ranks are ordered by their numbers as follows: $3<4<5<6<7<8<9<10<J<Q<K<A<2<\text{小王}<\text{大王}$, and suits do not affect card strength. In each game, a hand consists of $n$ cards. Each turn, a player may play cards according to certain allowed patterns. The side that first plays out all cards wins.

Now, Niuniu only wants to know, for several of his hands, the minimum number of plays needed to play out all the cards in each hand. Please help him solve this problem.

Note that in this problem, the set of playable patterns per move is similar to standard Dou Dizhu but slightly different. The specific rules are as follows:

In this problem, the two Jokers cannot form a pair.

Input Format

The first line contains $2$ positive integers $T, n$ separated by a space, representing the number of hands and the number of cards in each hand.

Then follow $T$ groups of data. For each group, there are $n$ lines, each containing a pair of non-negative integers $a_i, b_i$, representing one card, where $a_i$ is the card rank and $b_i$ is the suit, separated by a space. Specifically, we use $1$ to represent rank $A$, $11$ for $J$, $12$ for $Q$, and $13$ for $K$; Spades, Hearts, Clubs, and Diamonds are represented by $1$–$4$ respectively; the small Joker is represented as 0 1, and the big Joker as 0 2.

Output Format

Output $T$ lines. Each line contains one integer, the minimum number of plays needed to play out the $i$-th hand.

1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1

3

1 17
12 3
4 3
2 3
5 4
10 2
3 3
12 2
0 1
1 3
10 1
6 2
12 1
11 3
5 2
12 4
2 2
7 2

6

Hint

Sample 1 Explanation

There is $1$ hand containing $8$ cards: Diamonds $7$, Diamonds $8$, Spades $9$, Diamonds $10$, Spades $J$, Spades $5$, Diamonds $A$, and Spades $A$. You can play them out in $3$ moves by playing a single straight (Diamonds $7$, Diamonds $8$, Spades $9$, Diamonds $10$, Spades $J$), a single card (Spades $5$), and a pair (Spades $A$ and Diamonds $A$).

Constraints and Notes

For the first $20$ test points, the scales of the number of hands $T$ and the number of cards $n$ are as follows:

The testdata does not guarantee that all hands are randomly generated.

Translated by ChatGPT 5