#include <bits/stdc++.h>

using namespace std;

using i64=long long;
using u64=unsigned long long;
using db=double;
using pii=pair<int,int>;
using vi=vector<int>;

template<typename T>
inline T read(){
    T x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) x=x*10+(ch-'0'),ch=getchar();
    return f?-x:x;
}

#define rdi read<int>
#define rdi64 read<i64>
#define fi first
#define se second
#define pb push_back

const int N=1e5+10,L=21;

int n,m;

int pos[N*L*2],v[N*L*2],tot;
int _cnt[N*4],*cnt=_cnt+N*2;
pii val[N*2];int tot1;

void modify(int x,int to){
    --cnt[v[x]],++cnt[v[x]=to];
}

// Precondition: p > 1, m > 1
bool check(int p){
    static pii st[N*2];int tp=0;
    queue<int> q;
    for(int i=tot1-1;i>=0;i--){
        if(abs(val[i].se)>=p) q.push(val[i].fi);
        else break;
    }
    while(!q.empty()){
        int x=q.front();q.pop();
        if(abs(v[x])<p) continue;
        int nx=(x+1)%tot;
        st[++tp]={x,v[x]},st[++tp]={nx,v[nx]};
        modify(nx,v[nx]+v[x]/p),modify(x,v[x]%p);
        if(abs(v[nx])>=p) q.push(nx);
    }
    bool ret=(cnt[-p+1]==m||cnt[0]==tot||cnt[p-1]==m);
    while(tp){
        int x=st[tp].fi,y=st[tp].se;
        --cnt[v[x]],++cnt[v[x]=y],--tp;
    }
    return ret;
}

void clear(){
    for(int i=0;i<tot;i++)
        cnt[v[i]]=0,v[i]=0;
    tot=0;
}

void solve(){
    n=rdi(),m=rdi();
    i64 sum1=0;
    for(int i=0;i<n;i++){
        int b=rdi(),a=rdi();
        sum1+=b,val[i*2]={(a+1)%m,b},val[i*2+1]={a%m,-b};
    }
    if(m==1) {puts("-1");return;}
    n*=2;int len=__lg(n);
    sort(val,val+n),tot=0;
    for(int i=0,p=0;i<m;){
        while(p<n&&val[p].fi<=i) ++p;
        if((m+i-val[(p+n-1)%n].fi)%m<=len)
            pos[tot++]=i++;
        else if(p<n) i=val[p].fi;
        else break;
    }
    tot1=0;
    for(int l=0,r,j=0;l<n;l=r){
        while(pos[j]<val[l].fi) ++j;
        r=l;int sum=0;
        while(r<n&&val[l].fi==val[r].fi)
            sum+=val[r++].se;
        val[tot1++]={j,v[j]=sum};
    }
    for(int i=0;i<tot;i++)
        ++cnt[v[i]];
    sort(val,val+tot1,[&](pii a,pii b){
        return abs(a.se)<abs(b.se);
    });
    int ans=0;
    if(cnt[0]==tot) ans=-1;
    else{
        if(sum1%m==0) ++ans;
        for(int i=2;i<=n+1;i++)
            ans+=check(i);
    }
    cout<<ans<<'\n';
    clear();
}

int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    int T=rdi();
    while(T--) solve();
    return 0;
}