Description

Niuniu has recently become obsessed with a card game called Dou Dizhu. Dou Dizhu is a card game played with a standard deck consisting of spades, hearts, clubs, and diamonds from $A$ to $K$, plus the two jokers, for a total of $54$ cards. In Dou Dizhu, the rank order of the cards is represented by their face values as follows: $3<4<5<6<7<8<9<10<J<Q<K<A<2<\text{small Joker}<\text{big Joker}$, and suits do not affect the rank. In each round, a hand consists of $n$ cards. Each turn, a player may play according to the allowed patterns. The first player to play all of their cards wins the game.

Now, Niuniu only wants to know, for several sets of hands, the minimum number of plays required to play out each of them. Please help him solve this problem.

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

The testdata for this problem is random and hacks are not supported. To hack or use stronger testdata please click here.

Input Format

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

Then follow $T$ groups of data. Each group contains $n$ lines, each line containing a pair of nonnegative integers $a_i, b_i$ representing a card, where $a_i$ is the rank and $b_i$ is the suit, separated by a space. Specifically, we use $1$ to represent rank $A$, $11$ to represent rank $J$, $12$ to represent rank $Q$, and $13$ to represent rank $K$; spades, hearts, clubs, and diamonds are represented by $1$–$4$, respectively; the small joker is represented by 0 1, and the big joker is represented by 0 2.

Output Format

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

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 set with $8$ cards: diamond $7$, diamond $8$, spade $9$, diamond $10$, spade $J$, spade $5$, diamond $A$, and spade $A$. You can finish in $3$ plays by playing a straight of singles (diamond $7$, diamond $8$, spade $9$, diamond $10$, spade $J$), a single (spade $5$), and a pair (spade $A$ and diamond $A$).

For different test points, we define the scales of the number of hand sets $T$ and the number of cards $n$ as follows:

It is guaranteed that all hands are randomly generated.

Translated by ChatGPT 5