주식 차트 (Large)

신문의 연말 경제 결산 기사를 쓰면서 지난 한 해 동안 여러 주식의 가격이 어떻게 움직였는지 보여 주는 차트를 싣기로 했다. 주식 $n$개의 가격을 한 해의 같은 시점 $k$개에서 보여 준다.

주식 하나의 단순 차트는 점 $(0, price_0)$, $(1, price_1)$, ..., $(k-1, price_{k-1})$을 순서대로 선분으로 이은 그림이다. $price_i$는 그 주식의 $i$번째 시점 가격이다.

지면을 아끼려고 단순 차트 여러 개를 하나로 합친 겹친 차트를 만들었다. 겹친 차트는 담고 있는 주식마다 선을 하나씩 그린다. 어느 선이 어느 주식인지 헷갈리지 않도록, 한 겹친 차트 안에서는 두 선이 교차해서도 안 되고 서로 닿아서도 안 된다.

두 선이 교차하지도 닿지도 않는 것은 시점 $k$개 전부에서 한 주식의 가격이 다른 주식의 가격보다 항상 큰 경우와 같다.

주식 $n$개의 시점 $k$개 가격이 주어질 때, 모든 주식을 보여 주는 데 필요한 겹친 차트의 최소 개수를 구한다.

첫 줄에 테스트 케이스의 개수 $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}$는 $i$번째 주식의 시점 $j$ 가격을 나타내는 정수이다.

제한

• $1 \le T \le 100$
• $1 \le n \le 100$
• $2 \le k \le 25$
• $0 \le price_{i,j} \le 1000000$

각 테스트 케이스마다 Case #X: Y 형식으로 한 줄씩 출력한다. $X$는 1부터 시작하는 테스트 케이스 번호이고, $Y$는 주식 $n$개의 가격을 모두 보여 주는 데 필요한 겹친 차트의 최소 개수이다.