Problem Description

Cow Cow has recently become obsessed with a card game called Landlord. Landlord is a poker 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}$. The suit does not affect the card's rank. In each game, a player's hand consists of $n$ cards. Players can play cards according to specific patterns, and the first player to empty their hand wins.

Now, Cow Cow wants to know the minimum number of plays required to empty each of his several hands of cards. Please help him solve this problem.

It should be noted that the patterns of play in this problem are slightly different from the standard Landlord rules. Specifically:

In this problem, two jokers cannot be used as a pair.

Input Format

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

Next, there are $T$ groups 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$ is the card's rank and $b_i$ is the card's suit, separated by spaces. Specifically, we use $1$ for rank A, $11$ for rank J, $12$ for rank Q, and $13$ for 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 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 hand of 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 hand of 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).

Data Range and Hints

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

The data does not guarantee that all hands of cards are randomly generated.

见题面 Input 部分

见题面 Output 部分