#include <bits/stdc++.h>
#define il inline
#define B __int128
using namespace std;
il B read(){
    B x=0,c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-48,c=getchar();
    return x;
}
void write(B x){
    if(x>9) write(x/10);
    putchar(x%10+48);
}
il void print(B x,char c){write(x),putchar(c);}
il B qp(B a,B b,B mod){
    B ans=B(1);
    while(b){
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod,b>>=1;
    }
    return ans;
}
const int N=10;const B inf=1e6;
int T,n,ck;B p,m,a[N],b[N],c[N],cur[N],iv[N],ans;
B x,y,z,u,v,w,s,t;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);p=read(),m=B(sqrtl(p)),ans=0;
        for(int i=1;i<=n;++i) a[i]=read(),b[i]=read(),c[i]=read(),iv[i]=qp(a[i]+1,p,p-2);
        for(B i=min(inf,m);i;--i){
            ck=1;for(int j=1;j<=n;++j) cur[j]=(c[j]-a[j]*i%p*i%p+p)*iv[j]%p;
            for(int j=1;j<n;++j) if(cur[j]!=cur[j+1]){ck=0;break;}
            if(ck && i*i+cur[1]<p){ans=i*i+cur[1];break;}
            ck=1;for(int j=1;j<=n;++j) cur[j]=(c[j]-a[j]*i%p*i%p-a[i]*i%p+B(2)*p)*iv[i]%p;
            for(int j=1;j<n;++j) if(cur[j]!=cur[j+1]){ck=0;break;}
            if(ck && i*i+cur[1]+i<p){ans=i*i+cur[1]+i;break;}
            ck=1;x=i*i+B(2)*i;
            for(int j=1;j<=n;++j) if((a[i]*x%p)!=c[i]){ck=0;break;}
            if(ck && i*i+i*2<p){ans=i*i+cur[1]+i;break;}
        }
        print(ans,'\n');
    }
    return 0;
}