주사위 스트레이트 (Small)

시간 제한5초메모리 제한512 MB

요약

각 면에 서로 다른 여섯 개의 정수가 적힌 주사위 N개가 주어질 때, 각 주사위를 최대 한 번씩 사용해 윗면에 놓을 수 있는 가장 긴 연속된 정수 구간의 길이를 구한다.

문제

각 면에 서로 다른 양의 정수가 하나씩 적힌 주사위 $N$ 개가 있다. 주사위마다 적힌 수의 구성은 다를 수 있다.

주사위 중 일부 또는 전부를 한 줄로 늘어놓아 위를 향한 면의 수가 연속한 정수가 되게 만들려고 한다. 이렇게 만든 수열을 스트레이트라고 한다. 주사위마다 어느 면을 위로 둘지 자유롭게 고를 수 있고, 한 주사위는 많아야 한 번만 쓴다.

만들 수 있는 가장 긴 스트레이트의 길이를 구하라.

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 주사위의 개수 $N$ 이 주어진다. 다음 $N$ 개의 줄에는 각각 여섯 개의 양의 정수 $D_{ij}$ 가 주어진다. $i$ 번째 줄의 $j$ 번째 수는 $i$ 번째 주사위의 $j$ 번째 면에 적힌 수이다.

제한

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $y$ 는 만들 수 있는 가장 긴 스트레이트의 길이이다.

첫 번째 예제의 첫 테스트 케이스에서는 네 번째 주사위의 2, 세 번째 주사위의 3, 첫 번째 주사위의 4, 두 번째 주사위의 5를 골라 길이 4의 스트레이트를 만든다.

같은 예제의 두 번째 테스트 케이스에서는 길이 1짜리 스트레이트 말고는 아무것도 만들 수 없다.

세 번째 테스트 케이스에서는 한 주사위에서 1, 다른 주사위에서 2, 남은 주사위에서 3을 고르면 된다. 이 경우처럼 면에 적힌 수가 완전히 같은 주사위가 여러 개 있을 수 있다.

예제 1

입력

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