#include<bits/stdc++.h>
using namespace std;

int T;
int t1=3,N=2,M=1,V=2,D=1,C=1;
int ans=0;
int biaoji=0;
/*
特殊性质 A：保证 m = n，且对于任意的 j(1 ≤ j ≤ m)，都有 cj = j。
特殊性质 B：保证 dj = 1。

*/
int hs(int n,int m,int v)
{
	int c,d;
	for(int i=0;i<m;i++)
	{
		cin>>c>>d;
		
	}
	if(T==t1) 
	{
		if(n==N && m==M && V==v )
		{
			cout<<ans<<endl;
			if(biaoji==0)
			{
				biaoji++;
				M++;
				ans--;
			}
			else if(biaoji==1)
			{
				biaoji++;
				ans-=3;
			}
			else
			{
				biaoji=0;
				ans=0;//初始化 
			}
		}	
	}
	else
		cout<<(c+d)/n+m+ans<<endl; 
	return 0;
}

int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int n,m,v;
	ans=4;
	cin>>T;
	for(int i=0;i<T;i++)
	{
		cin>>n>>m>>v;
		hs(n,m,v);
	}
	return 0;
}

