题目描述

You have a special set of $N$ six-sided dice, each of which has six different positive integers on its faces. Different dice may have different numberings.

You want to arrange some or all of the dice in a row such that the faces on top form a straight (that is, they show consecutive integers). For each die, you can choose which face is on top.

How long is the longest straight that can be formed in this way?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case begins with one line with $N$, the number of dice. Then, $N$ more lines follow; each of them has six positive integers $D_{ij}$. The $j$-th number on the $i$-th of these lines gives the number on the $j$-th face of the $i$-th die.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the length of the longest straight that can be formed.

3
4
4 8 15 16 23 42
8 6 7 5 30 9
1 2 3 4 55 6
2 10 18 36 54 86
2
1 2 3 4 5 6
60 50 40 30 20 10
3
1 2 3 4 5 6
1 2 3 4 5 6
1 4 2 6 5 3

Case #1: 4
Case #2: 1
Case #3: 3

提示

Sample Explanation

In sample case #1, a straight of length $4$ can be formed by taking the $2$ from the fourth die, the 3 from the third die, the $4$ from the first die, and the $5$ from the second die.

In sample case #2, there is no way to form a straight larger than the trivial straight of length $1$.

In sample case #3, you can take a $1$ from one die, a $2$ from another, and a $3$ from the remaining unused die. Notice that this case demonstrates that there can be multiple dice with the same set of values on their faces.

Limits

• $1 \leq T \leq 100$.
• $1 \leq D_{ij} \leq 10^6$ for all $i, j$.

Small dataset (10 Pts, Test Set 1 - Visible)

• Time limit: 60 15 seconds.
• $1 \leq N \leq 100$.

Large dataset (15 Pts, Test Set 2 - Hidden)

• Time limit: 120 30 seconds.
• $1 \leq N \leq 50000$.
• The sum of $N$ across all test cases $\leq 200000$.