/*
n只小猪
f[i]: 打死i这个状态下的每个猪,所需最少的小鸟。---0011,杀死第1只和第2只
path[i][j]: 经过第i只猪和第j只猪的线都能经过经过那几只猪。---path[i][j]=0011,能经过第1只和第2只
PDD q[N]: 存每只猪的位置
转移:枚举每个状态state,
找到state不能走到的位置x(哪个位置为0)
枚举path[x][j], 0<j<n。所有能经过x的线
加进去的状态为 new_state = state | path[x][j]
f[new_state] = min(f[new_state], f[state] + 1);
*/
include
include
include
include
define x first
define y second
using namespace std;
typedef pair<double, double> PDD;
const int N = 18, M = 1 << N;
const double eps = 1e-8;
int n, m;
PDD q[N];
int pathN;
int f[M];
int cmp(double x, double y)
{
if(fabs(x - y) < eps) return 0;
if(x < y) return -1;
return 1;
}
int main()
{
int tt;
cin >> tt;
while(tt -- )
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
cin >> q[i].x >> q[i].y;
memset(path, 0, sizeof path);
for (int i = 0; i < n; i ++ )
{
path[i][i] = 1 << i; // 没有点和i组成抛物线,就自己为一条,只能经过自己
for (int j = 0; j < n; j ++ )
{
double x1 = q[i].x, y1 = q[i].y;
double x2 = q[j].x, y2 = q[j].y;
if(cmp(x1, x2) == 0) continue; // 两点不能竖直存在
double a = (y1 / x1 - y2 / x2) / (x1 - x2);
double b = y1 / x1 - a * x1;
if(cmp(a, 0) >= 0) continue; // 抛物线开口只能向下
int state = 0;
for (int k = 0; k < n; k ++ ) // 枚举哪个点能过这个线,就加上
{
double x = q[k].x, y = q[k].y;
if(cmp(a * x * x + b * x, y) == 0)
state += 1 << k;
}
path[i][j] = state;
}
}
memset(f, 0x3f, sizeof f);
f[0] = 0; //一个点没经过,需要0条抛物线
for(int i = 0; i < 1 << n; i ++ )
{
int x = 0;
for(int j = 0; j < n; j ++ ) // 找到不能经过的点
if((i >> j & 1) == 0)
{
x = j;
break;
}
for(int j = 0; j < n; j ++ ) // 状态转移
f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
}
for(int i = 0; i < 1 << n; i ++ )
{
int x = 0;
for(int j = 0; j < n; j ++ ) // 找到不能经过的点
if((i >> j & 1) == 0)
{
x = j;
break;
}
for(int j = 0; j < n; j ++ ) // 状态转移
f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
}
cout << f[(1 << n) - 1] << endl; // 111...111 所有点都能经过
}
return 0;
}