#include<bits/stdc++.h>
using namespace std;
int n,m;
#define fi first
#define se second
map<int,int>e;
int t[201000];
void ad(int x,int z){x%=m;t[e[x]+n]--,e[x]+=z,t[e[x]+n]++;}
vector<int>qb[200100];
#define pb push_back
void sol(){
    e.clear();
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n*2;i++)t[i]=0,qb[i].clear();
    t[n]=m;
    int al=0;
    for(int i=1,x,z;i<=n;i++)scanf("%d%d",&z,&x),ad(x,-z),ad(x+1,z),al+=z;
    if(t[n]==m){puts("-1");return;}
    for(auto it:e)if(it.se)qb[it.se+n].pb(it.fi);
    int ans=(al%m==0);
    vector<int>X;
    for(int i=n;i>=2;i--){
        for(int x:qb[i+n])X.pb(x);for(int x:qb[-i+n])X.pb(x);
        vector<int>Y=X;
        vector<pair<int,int> >xg;
        while(!Y.empty()){
            int u=Y.back(),v=(u+1)%m;Y.pop_back();
            int lj;if(e[u]>=i)lj=e[u]/i;else lj=-((-e[u])/i);
            t[e[u]+n]--;
            e[u]-=lj*i;xg.pb({u,-lj*i});
            t[e[u]+n]++;
            t[e[v]+n]--;
            bool fk=(abs(e[v])<i);
            xg.pb({v,lj});
            e[v]+=lj;fk&=(abs(e[v])>=i);
            t[e[v]+n]++;
            if(fk)Y.pb(v);
        }
        reverse(xg.begin(),xg.end());
        if(t[n]==m||t[n-(i-1)]==m||t[n+(i+1)]==m)ans++;
        for(auto it:xg){
            int x=it.first;
            t[e[x]+n]--,e[x]-=it.second,t[e[x]+n]++;
        }
    }
    printf("%d\n",ans);
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}