#include<cstdio>
#include<cstring>
#define MM 250

int m,r;

int father[MM*2];

struct  
{
	int left;
	int right;
	int rank;
}roots[MM*2];

void iniUnionSet()
{
	int i;
	int m2 = m*2;
	for(i=1;i<=m2;i++)
	{
		father[i] = i;
		roots[i].left = i<=m;
		roots[i].right = i>m;
		roots[i].rank = 1;
	}
}

int find(int x)
{
	if(father[x]!=x)
		father[x] = find(father[x]);
	return father[x];
}

void merge(int x,int y)
{
	int fx = find(x);
	int fy = find(y);
	if(fx==fy)return;
	if(roots[fx].rank>=roots[fy].rank)
	{
		father[fy] = fx;
		roots[fx].left+=roots[fy].left;
		roots[fx].right += roots[fy].right;
		roots[fx].rank += roots[fy].rank;
	}
	else
	{
		father[fx] = fy;
		roots[fy].left += roots[fx].left;
		roots[fy].right += roots[fx].right;
		roots[fy].rank += roots[fx].rank;
	}
}


struct
{
	int left;
	int right;
}group[MM*2];
int groupLen;
void grouping()
{
	int i,m2=m*2;
	groupLen = 0;
	for(i=1;i<=m2;i++)
	{
		if(i==father[i])
		{
			group[groupLen].left = roots[i].left;
			group[groupLen].right = roots[i].right;
			groupLen++;
		}
	}
}

void readData()
{
	int xi,yi;
	iniUnionSet();
	while(r--)
	{
		scanf("%d%d",&xi,&yi);
		merge(xi,yi+m);
	}
	grouping();
}

bool dp[MM][MM];
struct position
{
	int x;
	int y;
};

position feasible[MM*MM],future[MM*MM];
int fsLen,ftLen;
void dpProcess()
{
	int i,j;
	int nx,ny,m2=m/2;
	memset(dp,false,sizeof(dp));
	fsLen = ftLen =0;
	dp[0][0] = true;
	feasible[fsLen].x = 0;
	feasible[fsLen].y = 0;
	fsLen++;
	for(i=0;i<groupLen;i++)
	{
		ftLen = 0;
		for(j=0;j<fsLen;j++)
		{
			nx = feasible[j].x + group[i].left;
			ny = feasible[j].y + group[i].right;
			if(nx<=m2&&ny<=m2&&dp[nx][ny]==false)
			{
				dp[nx][ny] = true;
				future[ftLen].x = nx;
				future[ftLen].y = ny;
				ftLen++;
			}
		}
		for(j=0;j<ftLen;j++)
		{
			feasible[fsLen].x = future[j].x;
			feasible[fsLen].y = future[j].y;
			fsLen++;
		}
	}
}

void solve()
{
	int m2 = m/2;
	while(m2)
	{
		if(dp[m2][m2])
		{
			printf("%d\n",m2);
			break;
		}
		m2--;
	}
}

int main()
{
	int css;
	scanf("%d",&css);
	while(css--)
	{
		scanf("%d%d",&m,&r);
		readData();
		dpProcess();
		solve();
	}
	return 0;
}