Stock Charts

You are writing your newspaper's end of year economics summary, and you want charts that show how different stocks moved over the last year. You will show the prices of $n$ stocks, all measured at the same $k$ points of the year.

A simple chart for one stock draws line segments through the points $(0, price_{i,0})$, $(1, price_{i,1})$, $\dots$, $(k-1, price_{i,k-1})$ in that order, where $price_{i,j}$ is the price of stock $i$ at time point $j$.

To save space you use an overlaid chart. An overlaid chart combines one or more simple charts and shows several stocks at once, one line per stock. So that no two stocks are confused, the lines inside one overlaid chart may not cross and may not touch.

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

The first line contains a single integer $T$, the number of test cases. $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]

The first line of a test case holds the number of stocks $n$ and the number of time points $k$. The next $n$ lines hold one stock's prices in time order. Every $price_{i,j}$ is an integer.

Limits

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

For each test case print one line of the form Case #X: Y, where $X$ is the test case number starting at 1 and $Y$ is the minimum number of overlaid charts needed to show every stock's prices.