/******************************************************************************
* Test solution for the Prison rearrangment problem in NWERC'03
* Author: Jimmy Mårdell
******************************************************************************/

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
	int N;
	cin >> N;
	while (N--) {	
		int m,r,best=0;
		cin >> m >> r;

		vector<bool> mark(m*2,false);
		vector< vector<int> > v(m*2);
		queue<int> q;
		bool ok[100][100];

		for(int i=0;i<100;i++)
			for(int j=0;j<100;j++)
				ok[i][j]=false;
		ok[0][0]=true;

		for(int i=0;i<r;i++) {
			int a,b;
			cin >> a >> b;
			v[a-1].push_back(b+m-1);
			v[b+m-1].push_back(a-1);
		}

		for(int i=0;i<2*m;i++) {
			if (mark[i]) continue;
			int p1=0,p2=0;
			q.push(i);
			mark[i]=true;
			while (!q.empty()) {
				int t=q.front();
				q.pop();
				if (t<m) p1++; else p2++;
				for(int j=0;j<v[t].size();j++)
					if (!mark[v[t][j]]) {
						mark[v[t][j]]=true;
						q.push(v[t][j]);
					}
			}
			for(int x=m/2-p1;x>=0;x--)
				for(int y=m/2-p2;y>=0;y--)
					if (ok[x][y]) {
						ok[x+p1][y+p2]=true;
						if (x+p1==y+p2 && x+p1>best) best=x+p1;
					}
		}
		cout << best << endl;
	}
	return 0;
}