주식 차트

민호는 주식 상품 $N$개를 가지고 있다. 상품마다 연간 주가가 시간순으로 $K$개씩 기록되어 있다.

민호는 상품별로 주가를 시간순으로 이은 선그래프를 그려서 주가 변동을 한눈에 보려고 한다. 상품 하나에 차트 하나를 쓰면 자리를 너무 많이 차지하므로, 모든 그래프를 최소한의 차트에 나눠 그리고 싶다.

선분이 겹치거나 교차하면 변동을 읽기 어렵다. 그래서 한 차트에 그린 그래프끼리는 서로 만나지 않아야 한다. 두 그래프가 한 점에서라도 닿으면 겹친 것으로 본다.

이 조건을 지켜 모든 주식 상품의 그래프를 그릴 때 차트가 최소 몇 개 필요한지 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에 $N$과 $K$가 공백으로 구분되어 주어진다 ($1 \le N \le 100$, $1 \le K \le 25$). $N$은 그림으로 정리할 주식의 개수, $K$는 상품마다 기록된 주가의 개수이다.

이어지는 $N$개의 줄에 각 상품의 주가가 주어진다. $i$번째 줄의 $j$번째 수 $P_{ij}$는 $i$번째 상품의 $j$번 시각의 주가이다 ($0 \le P_{ij} \le 1000000$).

각 테스트 케이스마다 모든 주가 그래프를 겹치거나 교차하지 않게 그리는 데 필요한 최소 차트 개수를 한 줄에 하나씩 출력한다.