#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(sqrt(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-2,p);
        for(B i=min(inf,m);i;--i){
            ck=1;for(int j=1;j<=1;++j) cur[j]=(c[j]-a[j]*i%p*i%p+p)%p*iv[j]%p;
            //for(int j=1;j<=n;++j) if((a[j]*(i*i+cur[j])%p+cur[j])%p!=c[j]) puts("*");
            x=y=cur[1];
            for(int j=2;j<=n;++j){
                y=(x*y)%i;
                if(((a[j]*(i*i+x)%p+y)%p)!=c[j]){ck=0;break;}
            }
            if(ck && i*i+cur[1]<p){ans=i*i+cur[1];break;}
            ck=1;for(int j=1;j<=1;++j) cur[j]=(c[j]-a[j]*i%p*(i+1)%p+p)%p*iv[j]%p;
            x=y=cur[1];
            for(int j=2;j<=n;++j){
                y=(x*y)%i;
                if(((a[j]*(i*i+x)%p+y)%p)!=c[j]){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[j]*x%p)!=c[j]){ck=0;break;}
            if(ck && i*i+i*2<p){ans=i*i+2*i;break;}
        }
        print(ans,'\n');
    }
    return 0;
}
/*
1
5 923097614961380909
400075690252081333 1 336925156808111277
125871709464257940 1 69865713802049054
625686524906165721 1 231604442249496820
240111021937539825 1 466914943115931347
877342215923645363 1 405475742085577903
*/

answer.code: In function ‘int main()’:
answer.code:30:41: error: call of overloaded ‘sqrt(__int128&)’ is ambiguous
   30 |         scanf("%d",&n);p=read(),m=B(sqrt(p)),ans=0;
      |                                     ~~~~^~~
In file included from /usr/include/features.h:461,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/c++config.h:679,
                 from /usr/include/c++/13/cassert:43,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:33,
                 from answer.code:1:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:143:1: note: candidate: ‘double sqrt(double)’
  143 | __MATHCALL (sqrt,, (_Mdouble_ __x));
      | ^~~~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:114:
/usr/include/c++/13/cmath:1037:3: note: candidate: ‘constexpr __gnu_cxx::__bfloat16_t std::sqrt(__gnu_cxx::__bfloat16_t)’
 1037 |   sqrt(__gnu_cxx::__bfloat16_t __x)
      |   ^~~~
/usr/include/c++/13/cmath:943:3: note: candidate: ‘constexpr _Float128 std::sqrt(_Float128)’
  943 |   sqrt(_Float128 __x)
      |   ^~~~
/usr/include/c++/13/cmath:761:3: note: candidate: ‘constexpr _Float64 std::sqrt(_Float64)’
  761 |   sqrt(_Float64 __x)
      |   ^~~~
/usr/include/c++/13/cmath:667:3: note: candidate: ‘constexpr _Float32 std::sqrt(_Float32)’
  667 |   sqrt(_Float32 __x)
      |   ^~~~
/usr/include/c++/13/cmath:573:3: note: candidate: ‘constexpr _Float16 std::sqrt(_Float16)’
  573 |   sqrt(_Float16 __x)
      |   ^~~~
/usr/include/c++/13/cmath:442:3: note: candidate: ‘constexpr long double std::sqrt(long double)’
  442 |   sqrt(long double __x)
      |   ^~~~
/usr/include/c++/13/cmath:438:3: note: candidate: ‘constexpr float std::sqrt(float)’
  438 |   sqrt(float __x)
      |   ^~~~
answer.code:28:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   28 |     scanf("%d",&T);
      |     ~~~~~^~~~~~~~~
answer.code:30:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   30 |         scanf("%d",&n);p=read(),m=B(sqrt(p)),ans=0;
      |         ~~~~~^~~~~~~~~