#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

int n,m;
map<int,int>a,aa;
set<pii>s;

vi o;
void upd(int x,int y){
	o.pb(x);
	s.erase(mkp(a[x],x));
	a[x]+=y;
	if(a[x]) s.insert(mkp(a[x],x));
}
bool chk(int x)
{
	while(s.size()){
		if((s.begin())->fi<=-x){
			int w=s.begin()->se;
			upd(w,x);
			upd((w+1)%m,-1);
		}
		else if((--s.end())->fi>=x){
			int w=(--s.end())->se;
			upd(w,-x);
			upd((w+1)%m,1);
		}
		else break;
	}
	if(!s.size())return 1;
	// a[i] 全相同 & a[i]=-x+1,0,x-1
	if((s.begin()->fi)!=((--s.end())->fi))return 0;
	if((s.begin()->fi)==0)return 1;
	return s.size()==m && ((s.begin()->fi)==(x-1) || (s.begin()->fi)==(-x+1));
}

void clear(){
	for(auto t:o)
		s.erase(mkp(a[t],t)),s.insert(mkp(a[t]=aa[t],t));
	o.clear();
}

void work()
{
	n=read(),m=read(); a.clear(),s.clear();
	int f1=0;
	For(i,1,n){
		int c=read(),x=read();
		a[x%m]-=c,a[(x+1)%m]+=c,f1+=c;
	}
	int res=(f1%m==0);
	bool all0=1;
	for(auto t:a){
		if(t.se){
			all0=0;
			aa[t.fi]=t.se;
			s.insert(mkp(t.se,t.fi));
		}
	}
	a=aa;
	if(all0){
		puts("-1");
		return;
	}
	For(i,2,n+1){
		res+=chk(i);
		clear();
	}
	cout<<res<<'\n';
}

signed main()
{
	int T=read();
	while(T--)work();
    return 0;
}