#include <bits/stdc++.h>
using namespace std;
int T, n, m, cnt, t[405], dp[1 << 18];
double x[20], y[20];
int find(double xi, double yi, double xj, double yj) {
	const double p = xi * xi, q = xj * xj, r = q / p;
	xi *= r, yi *= r;
	if (fabs(xj - xi) < 1e-9) return 0;
	const double b = (yj - yi) / (xj - xi), a = (yj - b * xj) / q;
	if (a >= 0) return 0;
	int tmp = 0;
	for (int i = 1; i <= n; ++i) {
		if (fabs(a * x[i] * x[i] + b * x[i] - y[i]) < 1e-9) tmp |= (1 << n - i);
	}
	return tmp;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		cnt = 0;
		for (int i = 1; i <= n; ++i) scanf("%lf%lf", &x[i], &y[i]);
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j < i; ++j) {
				t[++cnt] = find(x[i], y[i], x[j], y[j]);
			}
			t[++cnt] = (1 << n - i);
		}
		memset(dp, 0x3f, sizeof(dp));
		dp[0] = 0;
		for (int i = 0; i < (1 << n); ++i) {
			for (int j = 1; j <= cnt; ++j) {
				if ((i | t[j]) != i) continue;
				dp[i] = min(dp[i], dp[i - t[j]] + 1);
			}
		}
		printf("%d\n", dp[(1 << n) - 1]);
	}
	return 0;
}

WA on #test 8, 95pts. 输入：

15
14 1
6.86 0.90
4.65 5.15
1.50 3.74
6.50 1.88
4.50 5.28
0.50 1.47
1.00 2.72
4.00 5.57
5.00 4.76
6.00 3.06
2.50 5.14
3.00 5.50
2.00 4.55
3.50 5.65
15 1
4.99 8.19
9.35 6.67
2.00 4.56
5.50 8.43
0.50 1.30
5.00 8.20
8.00 8.01
3.00 6.20
6.00 8.56
3.50 6.86
8.50 7.60
7.50 8.30
9.50 6.47
6.50 8.58
9.00 7.09
15 1
6.18 2.46
8.58 1.73
7.00 2.31
6.50 2.41
9.00 1.50
5.50 2.49
0.50 0.43
4.00 2.30
1.50 1.17
2.00 1.48
1.00 0.82
9.50 1.20
6.00 2.47
3.50 2.16
3.00 1.97
14 1
9.63 0.95
2.35 5.80
0.50 1.53
4.50 7.95
2.00 5.16
5.00 8.02
8.50 3.96
2.50 6.04
1.00 2.90
8.00 5.03
4.00 7.72
5.50 7.93
9.50 1.33
6.00 7.68
15 1
6.92 5.55
3.70 9.23
7.50 3.72
6.50 6.64
7.00 5.31
2.00 6.77
0.50 2.08
3.00 8.58
4.00 9.34
2.50 7.81
3.50 9.09
1.00 3.91
8.00 1.87
5.00 9.05
4.50 9.33
14 1
1.00 2.72
7.83 4.47
2.00 4.81
5.00 7.30
0.50 1.43
6.00 6.88
3.00 6.27
2.50 5.62
1.50 3.84
4.00 7.10
4.50 7.28
8.00 4.13
9.50 0.43
5.50 7.17
15 1
4.99 8.19
9.35 6.67
2.00 4.56
5.50 8.43
0.50 1.30
5.00 8.20
8.00 8.01
3.00 6.20
6.00 8.56
3.50 6.86
8.50 7.60
7.50 8.30
9.50 6.47
6.50 8.58
9.00 7.09
15 1
6.18 2.46
8.58 1.73
7.00 2.31
6.50 2.41
9.00 1.50
5.50 2.49
0.50 0.43
4.00 2.30
1.50 1.17
2.00 1.48
1.00 0.82
9.50 1.20
6.00 2.47
3.50 2.16
3.00 1.97
14 1
9.63 0.95
2.35 5.80
0.50 1.53
4.50 7.95
2.00 5.16
5.00 8.02
8.50 3.96
2.50 6.04
1.00 2.90
8.00 5.03
4.00 7.72
5.50 7.93
9.50 1.33
6.00 7.68
15 1
6.92 5.55
3.70 9.23
7.50 3.72
6.50 6.64
7.00 5.31
2.00 6.77
0.50 2.08
3.00 8.58
4.00 9.34
2.50 7.81
3.50 9.09
1.00 3.91
8.00 1.87
5.00 9.05
4.50 9.33
14 1
1.00 2.72
7.83 4.47
2.00 4.81
5.00 7.30
0.50 1.43
6.00 6.88
3.00 6.27
2.50 5.62
1.50 3.84
4.00 7.10
4.50 7.28
8.00 4.13
9.50 0.43
5.50 7.17
15 1
4.99 8.19
9.35 6.67
2.00 4.56
5.50 8.43
0.50 1.30
5.00 8.20
8.00 8.01
3.00 6.20
6.00 8.56
3.50 6.86
8.50 7.60
7.50 8.30
9.50 6.47
6.50 8.58
9.00 7.09
15 1
6.18 2.46
8.58 1.73
7.00 2.31
6.50 2.41
9.00 1.50
5.50 2.49
0.50 0.43
4.00 2.30
1.50 1.17
2.00 1.48
1.00 0.82
9.50 1.20
6.00 2.47
3.50 2.16
3.00 1.97
14 1
9.63 0.95
2.35 5.80
0.50 1.53
4.50 7.95
2.00 5.16
5.00 8.02
8.50 3.96
2.50 6.04
1.00 2.90
8.00 5.03
4.00 7.72
5.50 7.93
9.50 1.33
6.00 7.68
15 1
6.92 5.55
3.70 9.23
7.50 3.72
6.50 6.64
7.00 5.31
2.00 6.77
0.50 2.08
3.00 8.58
4.00 9.34
2.50 7.81
3.50 9.09
1.00 3.91
8.00 1.87
5.00 9.05
4.50 9.33

正确输出：

6
5
5
6
6
5
5
5
6
6
5
5
5
6
6

程序输出：

6
5
6
6
6
5
5
6
6
6
5
5
6
6
6

求调