Stock Charts

Minho owns $N$ stock products. Each product has $K$ yearly prices recorded in time order.

Minho wants to draw one line graph per product, joining that product's prices in time order, so he can read the price changes at a glance. Giving every product its own chart takes too much space, so he wants to spread all of the graphs over as few charts as possible.

Overlapping or crossing segments make the changes hard to read, so the graphs drawn on one chart must never meet. Two graphs count as overlapping if they touch at even a single point.

Find the smallest number of charts needed to draw the graphs of every stock product under this rule.

The first line contains the number of test cases $T$.

The first line of each test case contains $N$ and $K$ separated by a space ($1 \le N \le 100$, $1 \le K \le 25$). $N$ is the number of stocks to chart and $K$ is the number of prices recorded for each product.

Each of the next $N$ lines contains the prices of one product. The $j$-th number on the $i$-th line, $P_{ij}$, is the price of product $i$ at time $j$ ($0 \le P_{ij} \le 1000000$).

For each test case, print on its own line the minimum number of charts needed to draw every price graph without overlapping or crossing.