11008

#include <iostream>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>

#define INF 1000000

using namespace std;

int X[20],Y[20];
int totalpointsOfline[20][20];
int m,n,restTrees;
int dp[66000];

void init()
{
	memset(totalpointsOfline,0,sizeof(totalpointsOfline));
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			for(int k=n-1;k>=0;k--)
			{
				totalpointsOfline[i][j]<<=1;
				if( (Y[j]-Y[i])*(X[k]-X[i])==(Y[k]-Y[i])*(X[j]-X[i]))
				totalpointsOfline[i][j]+=1;
			}
		}
	}
	memset(dp,-1,sizeof(dp));
}

int _min(int a,int b)
{
	return a<b?a:b;
}

int DP(int totalTrees)
{
	if(dp[totalTrees]!=-1)
	return dp[totalTrees];

	int cnt=0;
	for(int i=0;i<n;i++)
	{
		if(totalTrees&(1<<i))
		cnt+=1;
	}
	if(cnt<=restTrees)
	return dp[totalTrees]=0;

	if(cnt==1)
	return dp[totalTrees]=1;

	int MX = INF;
	for(int i=0;i<n;i++)
	{
		if(totalTrees&(1<<i))
		{
			for(int j=i+1;j<n;j++)
			{
				if(totalTrees&(1<<j))
				{
					MX = _min(MX,DP( totalTrees&(~totalpointsOfline[i][j]) )+1);
				}
			}
		}
	}
	return dp[totalTrees]=MX;
}
int main()
{
	int t,kase=1;
	int idx,a,b;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		init();
		for(int i=0;i<n;i++)
		{
			scanf("%d%d",&X[i],&Y[i]);
		}
		init();
		restTrees = n-m;
		printf("Case #%d:\n",kase++);
		printf("%d\n",DP((1<<n)-1));
		if(t)
		printf("\n");
	}
	return 0;
}