#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
int T,n,m,c[N],p[N];
map<int,int> mp;
set<pair<int,int> > s;
set<pair<int,int> >:: iterator it;
struct node{
	bool op;pair<int,int> a;
};
vector<node> st;
bool chk(int x){
//	printf("Chk:%d\n",x);
//	for(auto t:mp)if(t.second)printf("%d %d\n",t.first,t.second);
	while((s.rbegin()->first>=x)||(s.begin()->first<=-x)){
		int u;
//		printf("%d %d %d %d\n",s.begin()->first,s.begin()->second,s.rbegin()->first,s.rbegin()->second);
		if(s.rbegin()->first>=x)u=s.rbegin()->second,st.push_back((node){1,*s.rbegin()}),s.erase(*s.rbegin());
		else u=s.begin()->second,st.push_back((node){1,*s.begin()}),s.erase(s.begin());
		int v=(u+1)%m,v1=mp[u],v2=mp[v];
		it=s.lower_bound(make_pair(v2,v));
		if(it!=s.end()&&it->first==v2&&it->second==v)st.push_back((node){1,*it}),s.erase(it);
		int to=(v1<0?(-v1)/x:-v1/x);
		pair<int,int> A=make_pair(v1+to*x,u),B=make_pair(v2-to,v);
//		printf("%d %d %d %d %d\n",u,v,mp[u],v1,to);
		s.insert(A),st.push_back((node){0,A}),mp[u]=v1+to*x;
		s.insert(B),st.push_back((node){0,B}),mp[v]=v2-to;
//		puts("Set:");
//		for(auto t:s)printf("%d %d\n",t.first,t.second);
//		puts("Map:");
//		for(auto t:mp)printf("%d %d\n",t.first,t.second);
	}
	int p1=s.begin()->first,p2=s.rbegin()->first,sz=s.size();
//	printf("Final:%d %d %d\n",p1,p2,sz);
	reverse(st.begin(),st.end());
	for(auto t:st){
//		printf("%d %d %d\n",t.op,t.a.first,t.a.second);
		if(t.op)mp[t.a.second]=t.a.first,s.insert(t.a);
		else mp[t.a.second]=0,s.erase(t.a);
	}
	st.clear();
	if(p1!=p2)return 0;
	if(!p1)return 1;
	if(max(p1,-p1)!=x-1)return 0;
	if(sz!=m)return 0;
	return 1;
}
int d[N];
signed main(){
	scanf("%d",&T);
	for(;T--;){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)scanf("%d%d",&c[i],&p[i]);
		int val=0,res=0;
		for(int i=1;i<=n;i++)val+=c[i];
		if(val%m==0)res=1;
		mp.clear();
		for(int i=1;i<=n;i++){
			mp[(p[i]+1)%m]+=c[i];
			mp[p[i]%m]-=c[i];
		}
		bool flg=1;
		for(auto t:mp)if(t.second){flg=0;break;}
		if(flg)res=-1;
		else{
			s.clear();
			for(auto t:mp)s.insert(make_pair(t.second,t.first));
			for(int i=2;i<=n;i++)res+=chk(i);
		}
		printf("%d\n",res);
	}
}