Statement
你正在撰写报纸的年终经济总结，并决定展示若干图表来演示不同股票在过去一年中的表现。你已经决定要展示 n 只不同股票的价格，它们都在一年中的相同 k 个时间点。
一只股票价格的*简单图表*会在点 (0, price), (1, price), ... , (k-1, price) 之间画线，其中 price 是该股票在第 *i* 个时间点的价格。
为了节省空间，你发明了*叠加图表*的概念。叠加图表是一张或多张简单图表的组合，展示多只股票的价格（只需为每只股票画一条线）。为了避免图表中显示的股票之间产生混淆，叠加图表中的线不能交叉或接触。
给定 *n* 只股票在 *k* 个时间点中每个时间点的价格列表，确定展示所有股票价格所需的最少叠加图表数量。
Input
输入的第一行将包含一个整数 T，即测试用例的数量。接下来是 T 个测试用例，每个用例在不同行上，格式如下：
``
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
``
其中 price 是整数，表示第 *i* 只股票在时间 *j* 的价格。
### 数据范围
- 1 ≤ T ≤ 100
- 2 ≤ k ≤ 25
- 0 ≤ price ≤ 1000000
- 1 ≤ n ≤ 16
- 1 ≤ n ≤ 100
Output
按测试用例顺序逐个输出答案。对于每个测试用例，输出一行，包含 *Y*，其中 *Y* 是展示所有股票价格所需的最少叠加图表数量。
Examples
Input
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 1Output
2
3
2Constraints
- Time limit: 10000 ms
- Memory limit: 1048576 KB
- Tag: dynamic-programming
- Tag: graph