Background

NOIP2015 Day1T3

Problem Description

Cow Cow has recently become obsessed with a poker game called Landlord. Landlord is a game played with 54 cards, including spades, hearts, clubs, diamonds from A to K, and two jokers (small and big). In Landlord, the rank of the cards is as follows: $3<4<5<6<7<8<9<10<J<Q<K<A<2<\text{Small Joker}<\text{Big Joker}$, and the suit does not affect the card's rank. In each game, a player's hand consists of $n$ cards. The player can play cards according to specific patterns, and the first one to empty their hand wins the game.

Now, Cow Cow wants to know, for several sets of his hand cards, the minimum number of plays required to empty them. Please help him solve this problem.

It should be noted that the patterns of cards a player can play in this problem are slightly different from the standard Landlord rules. The specific rules are as follows:

This problem's data is random and does not support hacking. For hacking or strong data, please click here.

Input Format

The first line contains two positive integers $T$ and $n$, separated by spaces, indicating the number of hand card sets and the number of cards in each set, respectively.

Next, there are $T$ sets of data, each consisting of $n$ lines. Each line contains a pair of non-negative integers $a_i$ and $b_i$, representing a card, where $a_i$ denotes the card's rank and $b_i$ denotes the card's suit, separated by spaces. Specifically, we use $1$ to represent the 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 by 0 1 and the big joker by 0 2.

Output Format

There are $T$ lines in total, each containing an integer representing the minimum number of plays required to empty the $i$-th set of hand cards.

Sample Input and Output

Input Sample #1

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

Output Sample #1

3

Input Sample #2

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

Output Sample #2

6

Notes

Sample 1 Explanation

There is 1 set of hand cards, containing 8 cards: diamond 7, diamond 8, spade 9, diamond 10, spade J, spade 5, diamond A, and spade A. It can be emptied in 3 plays by playing a single straight (diamond 7, diamond 8, spade 9, diamond 10, spade J), a single card (spade 5), and a pair (spade A and diamond A).

For different test points, the scale of $T$ and $n$ is as follows:

The data guarantees that all hand cards are randomly generated.

见题面 Input 部分

见题面 Output 部分