주사위 스트레이트

각 면에 서로 다른 양의 정수가 하나씩 적힌 특별한 육면체 주사위 N개가 있다. 서로 다른 주사위에는 서로 다른 숫자들이 적혀 있을 수 있다.

주사위의 일부 또는 전부를 한 줄로 배열하여 위쪽 면들이 스트레이트를 이루게 하려고 한다. 즉, 위쪽 면들에 연속된 정수들이 나타나야 한다. 각 주사위마다 어느 면을 위쪽으로 할지 선택할 수 있다.

이 방법으로 만들 수 있는 가장 긴 스트레이트의 길이는 얼마인가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 모든 i, j에 대해 1 ≤ $D_{ij}$ ≤ $10^{6}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 60초. 1 ≤ N ≤ 100.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 120초. 1 ≤ N ≤ 50000. 모든 테스트 케이스에 걸친 N의 합은 ≤ 200000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 주사위의 수 N이 있는 한 줄로 시작한다. 그다음 N개의 줄이 더 주어지며, 각 줄에는 양의 정수 여섯 개 $D_{ij}$가 있다. 이 줄들 중 i번째 줄의 j번째 수는 i번째 주사위의 j번째 면에 적힌 수를 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 만들 수 있는 가장 긴 스트레이트의 길이이다.

예제 케이스 #1에서는 네 번째 주사위의 2, 세 번째 주사위의 3, 첫 번째 주사위의 4, 두 번째 주사위의 5를 선택하여 길이가 4인 스트레이트를 만들 수 있다.

예제 케이스 #2에서는 길이가 1인 자명한 스트레이트보다 더 긴 스트레이트를 만들 방법이 없다.

예제 케이스 #3에서는 한 주사위에서 1를, 다른 주사위에서 2를, 아직 사용하지 않은 나머지 주사위에서 3를 선택할 수 있다. 이 케이스는 면에 적힌 값들의 집합이 같은 주사위가 여러 개 있을 수 있음을 보여 준다는 점에 유의한다.