Description

你正在撰写报社的年度经济总结，目前你决定用几张图表来展示不同股票在过去一年的表现。你已经决定要展示 $n$ 支不同股票在一年中 $k$ 个时刻的价格。

一支股票的简单走势图，就是在平面上连接 $(0, \text{price}_0)$、$(1, \text{price}_1)$、……、$(k-1, \text{price}_{k-1})$ 这些点，其中 $\text{price}_i$ 表示该股票在第 $i$ 个时刻的价格。

为了节省版面，你发明了“叠加图表”的概念。一个叠加图表是由一条或多条简单走势图组成的，展示多支股票的价格（每支股票画一条线）。为了避免混淆，叠加图表中的不同股票曲线不能相交或相触。

给定 $n$ 支股票在 $k$ 个时刻的价格，请你计算，至少需要多少张叠加图表，才能展示所有股票的价格。

Input Format

输入的第一行为一个整数 $T$，表示测试用例数。接下来是 $T$ 组测试数据，每组格式如下：

$n\ k$

$\text{price}_{0,0}\ \text{price}_{0,1}\ \ldots\ \text{price}_{0,k-1}$

$\text{price}_{1,0}\ \text{price}_{1,1}\ \ldots\ \text{price}_{1,k-1}$

……

$\text{price}_{n-1,0}\ \text{price}_{n-1,1}\ \ldots\ \text{price}_{n-1,k-1}$

其中 $\text{price}_{i,j}$ 为第 $i$ 支股票在第 $j$ 个时刻的价格。

Output Format

对于每组测试数据，输出一行：

Case #$X$: $Y$

其中 $X$ 是测试用例编号（从 1 开始），$Y$ 是展示所有股票价格所需的最少叠加图表数。

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

Hint

限制条件

• $1 \leq T \leq 100$
• $2 \leq k \leq 25$
• $0 \leq \text{price}_{i,j} \leq 1000000$

小数据集

• 时间限制：2 秒
• $1 \leq n \leq 16$

大数据集

• 时间限制：3 秒
• $1 \leq n \leq 100$

翻译由 ChatGPT-4.1 完成。