12988번 - 주식 차트

민호는 N개의 주식 상품을 가지고 있다.  그리고 모든 상품들은 연간 주가가 시간순으로 K개 기록이 되어 있다.

민호는 각 상품들의 주가를 시간순으로 잇는 선그래프들을 그려 주가 변동을 한눈에 보고 싶어졌다.

한 개의 상품마다 한 개의 차트를 사용하기에는 공간을 너무 많이 차지하기 때문에 민호는 최소한의 차트를 이용해 모든 주식의 변동 그래프를 그리고 싶었다.

하지만 선분이 겹치거나 교차해 버리면 주식의 변동 그래프를 보기 힘들기 때문에 한 차트 그려지는 그래프들은 서로 겹치지 않게 하고 싶다.

이런 조건을 지켜 모든 주식상품들의 그래프를 그릴 때 최소 몇 개의 차트가 필요한지 알아보자.

첫 번째 줄에 테스트 케이스 T가 들어온다.

각 테스트케이스의 첫 번째 줄에는 N, K ( 1 ≤ N ≤ 100, 1 ≤ K ≤ 25 ) 가 공백을 구분으로 주어진다. 이는 각각 민호가 그림으로 정리하고 싶어하는 주식의 개수와 각 주식 상품들마다 기록이 되어있는 주가들의 개수이다.

두 번째 줄부터 N개의 줄에 걸쳐 P_ij (0 ≤ P_ij ≤ 1000000 ) 가 주어진다. P_ij는 i번째 상품이 j번 시간일때 주가를 의미한다.

모든 주식 상품을 주가변동을 선 그래프로 그렸을 때 겹치거나 교차하지 않게 그릴 수 있는 최소한의 차트의 개수를 출력한다.