SP7556 HASTOCK - B - Stock Charts

**B - Stock Charts** You're in the middle of writing your newspaper's end-of-year economics summary, and you've decided that you want to show a number of charts to demonstrate how different stocks have performed over the course of the last year. You've already decided that you want to show the price of **n** different stocks, all at the same **k** points of the year. A _simple chart_ of one stock's price would draw lines between the points (0, price $ _{0} $ ), (1, price $ _{1} $ ), ... , (k-1, price $ _{k-1} $ ), where price $ _{i} $ is the price of the stock at the _i_th point in time. In order to save space, you have invented the concept of an _overlaid chart_. An overlaid chart is the combination of one or more simple charts, and shows the prices of multiple stocks (simply drawing a line for each one). In order to avoid confusion between the stocks shown in a chart, the lines in an overlaid chart may not cross or touch. Given a list of _n_ stocks' prices at each of _k_ time points, determine the minimum number of overlaid charts you need to show all of the stocks' prices. Input The first line of input will contain a single integer **T**, the number of test cases. After this will follow **T** test cases on different lines, each of the form: ``` n k price0,0 price0,1 ... price0,k-1 price1,0 price1,1 ... price1,k-1 ... pricen-1,0 pricen-1,1 ... pricen-1,k-1 ``` Where price $ _{i,j} $ is an integer, the price of the _i_th stock at time _j_. Output For each test case, a single line containing "Case #X: Y", where _X_ is the number of the test-case (1-indexed) and _Y_ is the minimum number of overlaid charts needed to show the prices of all of the stocks. Limits 1 T 2 k 0 1 n Sample Input Output ` 3

3 4

1 2 3 4

2 3 4 6

6 5 4 3

3 3

5 5 5

4 4 6

4 5 4

5 2

1 1

2 2

5 4

4 4

4 1

` ` Case #1: 2

Case #2: 3

Case #3: 2`

N/A

N/A