주식 차트

신문의 연말 경제 결산 기사를 쓰면서, 지난 한 해 동안 주가가 어떻게 움직였는지 보여줄 그래프를 넣기로 했다. 종목 $n$개의 가격을 한 해의 같은 시점 $k$곳에서 측정한 값을 쓴다.

한 종목의 단순 차트는 점 $(0, price_{i,0})$, $(1, price_{i,1})$, $\dots$, $(k-1, price_{i,k-1})$을 차례대로 선분으로 이은 그림이다. 여기서 $price_{i,j}$는 $i$번 종목의 $j$번째 시점 가격이다.

지면을 아끼려고 겹친 차트를 쓴다. 겹친 차트는 단순 차트 하나 이상을 한 그림에 겹쳐 그린 것으로, 여러 종목의 가격을 종목마다 선 하나씩 그려서 보여준다. 어느 선이 어느 종목인지 헷갈리지 않도록, 한 겹친 차트 안의 선은 서로 교차하거나 닿아서는 안 된다.

종목 $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]

첫 줄에 종목 수 $n$과 시점 수 $k$가 주어지고, 다음 $n$개 줄에 각 종목의 가격이 시점 순서대로 주어진다. $price_{i,j}$는 정수이다.

제한

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

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