#include<bits/stdc++.h>
using namespace std;
int a[100005];
int t[200005];
int ans = 0;

int XYJ(){
	int s, f;
	cin >> s >> f;
	if(s == 0){
		return f == 1 ? 14 : 15;
	}else if(s == 1){
		return 12;
	}else if(s == 2){
		return 13;
	}else{
		return s - 2;
	}
}

void dfs(int x, int sum){
	if(x == 0){
		ans = min(ans, sum);
		return ;
	}
	
	int l, r, bg = 0;
	
	int xx = 0, d = -1;
	
	for(int i = 1; i <= 12; i++){
		if(t[i]){
			if(d == -1)d = i;
			xx++;
		}else{
			if(xx > bg){
				bg = xx;
				l = d;
				r = i - 1;
			}
			xx = 0;
			d = -1;
		}
	}
	
	bool _3 = 1, _2 = 1;
	for(int i = l; i <= r; i++){
		if(t[i] < 3){
			_3 = 0;
		}
		if(t[i] < 2){
			_2 = 0;
		}
	}
	if(_3 && bg >= 2){//Èý˳ 
		for(int i = l; i <= r; i++){
			t[i] -= 3;
		}
		dfs(x - 3 * (r - l + 1), sum + 1);
		for(int i = l; i <= r; i++){
			t[i] += 3;
		}
	}else if(_2 && bg >= 3){//¶þ˳ 
		for(int i = l; i <= r; i++){
			t[i] -= 2;
		}
		dfs(x - 2 * (r - l + 1), sum + 1);
		for(int i = l; i <= r; i++){
			t[i] += 2;
		}
	}else if(bg >= 5){//µ¥Ë³ 
		for(int i = l; i <= r; i++){
			t[i]--;
		}
		dfs(x - (r - l + 1), sum + 1);
		for(int i = l; i <= r; i++){
			t[i]++;
		}
	}
	
	for(int k = 1; k <= 15; k++){
		if(t[k] >= 4){
			t[k] -= 4;
			//ËÄ´ø¶þ 
			for(int i = 1; i <= 15; i++){
				for(int j = 1; j <= 15; j++){
					if((i == j && t[i] < 2) || !t[i] || !t[j]){
						continue;
					}
					t[i]--;t[j]--;
					dfs(x - 6, sum + 1);
					t[i]++;t[j]++;
				}
			}
			
			//Õ¨µ¯ 
			dfs(x - 4, sum + 1);
			
			t[k] += 4;
		}

		if(t[k] >= 3){
			t[k] -= 3;
			
			//Èý´ø¶þ 
			for(int i = 1; i <= 15; i++){
				if(t[i] < 2){
					continue;
				}
				t[i]-= 2;
				dfs(x - 5, sum + 1);
				t[i]+= 2;
			}
			
			//Èý´øÒ» 
			for(int i = 1; i <= 15; i++){
				if(!t[i]){
					continue;
				}
				t[i]--;
				dfs(x - 4, sum + 1);
				t[i]++;
			}
			
			//µ¥Èý 
			dfs(x - 3, sum + 1);
			
			t[k] += 3;
		}
		
		//¶Ô×Ó 
		if(t[k] >= 2){
			t[k] -= 2;
			dfs(x - 2, sum + 1);
			t[k] += 2;
		}
		
		//µ¥ÅÆ 
		if(t[k] >= 1){
			t[k]--;
			dfs(x - 1, sum + 1);
			t[k]++;
		}
	}
	
	if(t[15] >= 1 && t[14] >= 1){
		t[15]--;t[14]--;
		dfs(x - 2, sum + 1);
		t[15]++;t[14]++;
	}
	
}

int main(){
	int n, T;
	cin >> T >> n;
	while(T--){
		ans = 1145141919;
		for(int i = 1; i <= n; i++){
			a[i] = XYJ();
			t[a[i]]++;
		}
		
		dfs(n, 0);
		
		cout << ans << endl;
		
		for(int i = 0; i <= 15; i++){
			t[i] = 0;
		}
	}
	return 0;
}

提交后一会25一会20一会15一会10