#include <bits/stdc++.h>
using namespace std;
int n , m;
const int D = 30;
typedef long double db;
map<int,int> mp;
const int px[] = {1000000007 , 1000000009 , 998244353} ;
const int pl = 3;

int qpow(int a,int b,int mod) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1LL * ans * a %mod;
        a = 1LL * a * a % mod ;b >>= 1;
    }
    return ans;
}

bool check(int x) {
    vector<int> v , v2;
    for(int i = 0;i < pl;i++) {
        int p = px[i] , ans = 0;
        for(auto [a,c] : mp) {
            ans = (ans + 1LL * ((c + p) % p) * qpow(x , a , p) % p) % p;

        }
        ans = 1LL * ans * qpow((qpow(x , m , p) - 1 + p) % p , p - 2 , p)  % p;

        v.push_back(ans) ;
        v2.push_back((p - ans) % p) ;
        // printf("x = %d , ans = %d , p = %d\n",x,ans,p) ;
    }
    bool ff = 1;
    for(int i = 1;i < pl;i++) {
        if(v[i] != v[i - 1]) ff = 0;
    }
    if(ff) return 1;
    ff=1;
    for(int i = 1;i < pl;i++) {
        if(v2[i] !=  v2[i - 1]) ff = 0;
    }
    return ff;
}
typedef long long ll;
const int inf = 1e9;
int qpow2(int a,int b) {
    ll ret = 1;
    while(b) {
        if(b & 1) ret = min((ll)inf , ret * a);
        a = min((ll)inf , 1LL * a * a);
        b >>= 1;
    }
    return ret;
}
bool is_root(int x) {
    auto it = mp.end() ; it-- ;
    ll ans = 0;
    while(1) {
        ans = (ans + it->second) ;
        int nx = (it == mp.begin() ? it->first : it->first - prev(it)->first);
        ans *= qpow2(x , nx) ;
        if(abs(ans) > 1e9) return 0;
        if(it == mp.end())
            break;
        it--;
    }
    if(ans == 0) return 1;
    return 0;
}
typedef pair<int,int> pii;
const db eps = 1e-4;
mt19937 rnd( time(0)) ;
void solv() {
    cin >> n >> m;
    mp.clear() ;
    int ans = 0;
    int sol = 0;
    for(int i = 1;i <= n;i++) {
        int c , a;
        cin >> c >> a;
        // c = rnd()%2 ? 1 : -1 ;
        // a = rnd()%m;
        sol = (sol + c) % m;
        mp[a % m] += c; 
        mp[(a + 1) % m] -= c;
    }
    if(sol == 0) ans++ ;

    bool ff = 1;
    for(auto [x,y] : mp) {
        ff &= (y == 0) ;
    }
    if(ff) {
        cout << -1 << '\n' ; return ;
    }
    if(m <= 12) {
        for(int i = 2;i <= n*2 + 5;i++) ans += check(i) ;
        cout << ans << '\n' ; return ;
    }
    auto it = mp.lower_bound(m - D) ;
    vector<pii> coe;
    while(it != mp.end()) {
        coe.push_back(*it);
        it++ ;
    }
    // for(auto [a,c] : coe) cout << c <<' ' << a << '\n' ;
    for(int i = 2;i <= n * 2 + 5;i++) {
        if(i <= 12) ans += check(i) ;
        else {
            db sol = 0;
            int lst = D + 1;
            for(auto [a,c] : coe) {
                a = m - a;
                while(lst > a + 1) {
                    sol = sol / i ; lst-- ;
                }
                sol = (sol + c) / i; lst-- ;
            }
            while(lst > 1) {
                sol /= i ; lst-- ;
            }
            int dd = round(sol) ;
            if(fabs(sol - dd) < eps && dd != 0) {
                // cout << i <<' ' << sol << endl;
                ans += check(i);
            }
            else if(dd == 0) {
                ans += is_root(i) ;
            }
        }
    }
    cout << ans << '\n';
    return ;
}
int main() {
    ios::sync_with_stdio(false) ; cin.tie(0) ;
    int t;cin >> t;
    while(t--) solv() ;
    
}