#include <bits/stdc++.h>

using namespace std;
const int N = 3e5;
const double eps = 1e-7;
int t;
int main(){
	cin >> t;
	while(t--){
		int n,dp[N],sum[20][20][20] = {0},l[20][20] = {0},m,s[20][20] = {0},h[20] = {0};
		double x[20],y[20];
		cin >> n >> m;
		for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
		for (int i = 1; i <= n; i++){
			for (int j = i+1; j <= n; j++){
			double a = (y[i] * x[i] * x[i] * x[j] - y[j] * x[i] * x[i] * x[i]) / (x[i] * x[i] * (x[i] * x[i] * x[j] - x[i] * x[j] * x[j]));
			double b = (y[j] * x[i] * x[i] - y[i]* x[j] * x[j]) / (x[i] * x[i] * x[j] - x[i] * x[j] * x[j]);
			if (a >= 0){
				continue;
			}
			s[i][j] = 1;
			h[i] = 1;
			h[j] = 1;
			for (int k = 1; k <= n; k++){
				if (i == k || j == k) continue;
				double c = a*x[k]*x[k]+b*x[k];
				if (abs(y[k]-c) <= eps){
					l[i][j]++;
					sum[i][j][l[i][j]] = k;
				}
			}
			}
		}
		//for (int i = 1; i <= n; i++) cout << h[i] << " ";
		memset(dp,0x3f,sizeof(dp));
		dp[0] = 0;
		for (int i = 0; i < (1 << n); i++){
			for (int j = 1; j <= n; j++){
				
				if (h[j] == 0){
					dp[(i | (1 << (n-j)))] = min(dp[(i | (1 << (n-j)))],dp[i]+1);
					continue;
				} 
				for (int k = j+1; k <= n; k++){
					if (s[j][k] == 0) continue;
					if(h[k] == 0) continue;
				int d = i;
				d|=(1 << (n-j));
				d|=(1 << (n-k));
				for (int g = 1; g <= l[j][k]; g++){
					d|=(1 << (n-sum[j][k][g]));
				}
				dp[d] = min(dp[d],dp[i]+1);
				}
			}
		}
		cout << dp[(1 << n)-1] << endl;
	}
	
	
	return 0;
} 

wa 2 把测试点下了下来 发现和答案一摸一样 不知哪错了