주식 차트

신문의 연말 경제 요약 기사를 작성하던 중, 지난 한 해 동안 서로 다른 주식들의 실적이 어떠했는지 보여 주기 위해 여러 차트를 싣기로 했다. 이미 서로 다른 n개 주식의 가격을 한 해의 동일한 k개 시점에서 보여 주기로 했다.

한 주식의 가격을 나타내는 단순 차트는 점 (0, $price_{0}$), (1, $price_{1}$), ... , (k-1, $price_{k-1}$) 사이에 선을 그린다. 여기서 $price_{i}$는 i번째 시점에서 해당 주식의 가격이다.

공간을 절약하기 위해 중첩 차트라는 개념을 만들었다. 중첩 차트는 하나 이상의 단순 차트를 결합한 것으로, 여러 주식의 가격을 보여 준다(각 주식마다 선을 하나씩 그리기만 하면 된다). 차트에 표시된 주식들을 혼동하지 않도록 중첩 차트의 선들은 서로 교차하거나 닿아서는 안 된다.

k개의 각 시점에서 n개 주식의 가격 목록이 주어질 때, 모든 주식의 가격을 보여 주는 데 필요한 중첩 차트 수의 최솟값을 구한다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100 2 ≤ k ≤ 25 0 ≤ $price_{i,j}$ ≤ 1000000

작은 입력

시간 제한: 20초. 1 ≤ n ≤ 16

큰 입력

시간 제한: 30초. 1 ≤ n ≤ 100

입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 하나의 정수 T가 주어진다. 그 뒤에는 각각 다음 형식인 T개의 테스트 케이스가 서로 다른 줄에 주어진다.

n k
price_{0,0} price_{0,1} ... price_{0,k-1}
price_{1,0} price_{1,1} ... price_{1,k-1}
...
price_{n-1,0} price_{n-1,1} ... price_{n-1,k-1}

여기서 $price_{i,j}$는 시간 j에서 i번째 주식의 가격을 나타내는 정수이다.

각 테스트 케이스마다 "Case #X: Y"을 포함하는 한 줄을 출력한다. 여기서 X는 테스트 케이스의 번호(1-기준)이고, Y는 모든 주식의 가격을 보여 주는 데 필요한 중첩 차트 수의 최솟값이다.