记录编号	355425	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	Cydiater	是否通过	通过
代码语言	C++	运行时间	2.804 s
提交时间	2016-11-25 13:04:24	内存使用	30.70 MiB

//angrybirds
//by Cydiater
//2016.11.20
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <ctime>
#include <cmath>
#include <queue>
#include <map>
#include <bitset>
#include <set>
using namespace std;
#define ll long long
#define up(i,j,n)		for(ll i=j;i<=n;i++)
#define down(i,j,n)		for(ll i=j;i>=n;i--)
#define cmax(a,b)		a=max(a,b)
#define cmin(a,b)		a=min(a,b)
#define FILE "angrybirds"
#define eps 1e-6
const int MAXN=25;
const int MAXX=1<<18+5;
inline int read(){
	char ch=getchar();int x=0,f=1;
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int N,M,S[MAXN][MAXN],f[MAXX],T,top[MAXN];
struct XY{
	double x,y;
}xy[MAXN];
namespace solution{
	void init(){
		N=read();M=read();
		memset(top,0,sizeof(top));
		memset(f,10,sizeof(f));f[0]=0;
		up(i,0,N-1)scanf("%lf %lf",&xy[i].x,&xy[i].y);
		up(i,0,N-1){
			xy[i].x*=100;
			xy[i].y*=100;
		}
	}
	inline bool OK(double a,double b,XY t){
		double x=t.x,y=t.y;
		if(abs(y-(x*x*a+b*x))<=eps)return 1;
		return 0;
	}
	void slove(){
		up(i,0,N-1){
			S[i][++top[i]]=(1<<i);
			up(j,i+1,N-1){
				double x=xy[i].x,y=xy[i].y,_x=xy[j].x,_y=xy[j].y;
				if(x*_x==0||x-_x==0)continue;
				double a=y/(x*(x-_x))-_y/(_x*(x-_x)),b=y/x-a*x;
				if(a+eps>=0)continue;
				int ss=0;
				up(k,0,N-1)if(OK(a,b,xy[k]))ss|=(1<<k);
				S[i][++top[i]]=ss;
			}
		}
		up(i,0,(1<<N)-1)
			up(j,0,N-1)if(((1<<j)&(i))!=(1<<j)){
				up(k,1,top[j])cmin(f[(i|S[j][k])],f[i]+1);
				break;
			}
	}
	void output(){
		printf("%d\n",f[(1<<N)-1]);
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	using namespace solution;
	T=read();
	while(T--){
		init();
		if(N==1){puts("1");continue;}
		slove();
		output();
	}
	return 0;
}