Stock Charts (Large)

You are writing your newspaper's end of year economics summary, and you want to include charts that show how several stocks moved over the past year. You will show the price of $n$ different stocks at the same $k$ points of the year.

A simple chart of one stock draws line segments through the points $(0, price_0)$, $(1, price_1)$, ..., $(k-1, price_{k-1})$, where $price_i$ is the price of that stock at the $i$th point in time.

To save space you combine several simple charts into one overlaid chart, which draws one line for each stock it contains. So that the stocks stay distinguishable, no two lines inside one overlaid chart may cross, and no two lines may touch.

Two lines neither cross nor touch exactly when one of the two stocks is strictly more expensive than the other at all $k$ points in time.

Given the prices of $n$ stocks at each of $k$ points in time, find the minimum number of overlaid charts needed to show every stock.

The first line contains one integer $T$, the number of test cases. Then $T$ test cases follow, each in this form:

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}$ is an integer, the price of the $i$th stock at time $j$.

Limits

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

For each test case, print one line Case #X: Y, where $X$ is the number of the test case starting from 1 and $Y$ is the minimum number of overlaid charts needed to show the prices of all $n$ stocks.