Coding is the closest thing we have to superpower !

3841 : 状压dp-练习-直线刷点
描述

二维平面上有N个的点(可能存在重复的点),有一把刷子,刷一次可以把一条直线上的所有点都刷掉。问最少刷多少次,可以把全部的点都刷完。

输入

第一行有一个整数T(1 \le T \le 1000),表示数据的组数。

对于每一组数据:

第一行一个整数N(1 \le N \le 16)

接下来N行,每行给出一个整点坐标(x_i, y_i), |x_i|, |y_i| \le 20

输出

对于每一组数据,输出答案占一行。

样例

输入

2
3
0 0
1 1
2 2
3
0 0
1 1
2 3

输出

1
2
标签
语言:
主题: