#include <iostream>
#include <algorithm>
#include <functional>
#include <random>
#include <string>
#define qaq inline
using ll=long long;
const int sz=1e5+19;
int T;
ll m,p,err;
stdmt19937_64 engine(19990919);
struct info{
ll a,c,cnt;
bool operator==(const info &x)const{ return ax.a; }
bool operator<(const info &x)const{ return a<x.a; }
}pswz[sz],mvpswz[sz];
qaq ll mdl(ll x){
ll res=x+(x>>63&p);
return (res<p)?res:(res-p);
}
qaq ll mul(ll a,ll b){
a%=p,b%=p;
ll d=(static_cast<long double>(a)/pb+0.25);
ll res=ab-dp;
return (res<0)?(res+p):res;
}
bool check(ll x){
for(int cx=0;cx<m;++cx){
ll cur=mdl(mul(pswz[cx].a,x)-pswz[cx].c);
if(cur>err&&cur<p-err) return false;
}
return true;
}
bool mulLessThan(ll x,ll y,ll z){
return static_cast<long double>(x)y<=z1.01&&xy<=z;
}
void distribute(ll a,ll c,ll cnt,ll &ln,ll &rn){
if(!mulLessThan(cnt,err<<1,(a1)?p:(p>>1))) return;
if(!mulLessThan(rn-ln+1,a,p)) return;
ll gln=mul(ln,a),grn=mul(rn,a);
while(grn<gln) grn+=p;
ll rg=cnt*err,rln=c-rg,rrn=c+rg;
while(rln>grn) rln-=p,rrn-=p;
while(rrn<gln) rln+=p,rrn+=p;
if(gln<=rrn-p||rln+p<=grn) return;
if(rln>gln) ln+=(rln-gln)/a;
if(rrn<grn) rn-=(grn-rrn)/a;
}
stdbasic_string<info> arr;
void guessX(ll &ln,ll &rn){
static stdfunction<void(ll,ll,ll)> insert;
insert=[&ln,&rn](ll a,ll c,ll cnt)->void{
arr.push_back(info{a,c,cnt});
distribute(a,c,cnt,ln,rn);
};
stduniform_int_distribution<ll> uni4mp(0,p-1);
stduniform_int_distribution<ll> uni4mm(0,m-1);
arr.clear();
ll ofst=uni4mp(engine);
if((rn-ln)<(p>>2)) ln+=ofst,rn+=ofst;
else ln=0,rn=p-1;
for(int cx=0;cx<m;++cx){
mvpswz[cx]=pswz[cx];
mvpswz[cx].c=mdl(pswz[cx].c+mul(pswz[cx].a,ofst));
}
for(int cx=0;cx<20000;++cx){
ll att=0,ctt=0;
for(int cy=0,hist[3],id;cy<3;++cy){
stdfunction<bool(int)> idcheck;
idcheck=[&hist](int cy)->bool{
for(int t=0;t<cy;++t){
if(hist[t]==hist[cy]) return true;
}
return false;
};
do{
id=uni4mm(engine);
hist[cy]=id;
}while(idcheck(cy));
if(engine()&1){
att=mdl(att+mvpswz[id].a);
ctt=mdl(ctt+mvpswz[id].c);
}else{
att=mdl(att-mvpswz[id].a);
ctt=mdl(ctt-mvpswz[id].c);
}
}
insert(att,ctt,3);
}
for(int t=0;t<5;++t){
if(arr.size()>3000){
stdnth_element(arr.begin(),arr.begin()+3000,arr.end());
arr.resize(3000);
}
stdsort(arr.begin(),arr.end());
arr.erase(stdunique(arr.begin(),arr.end()),arr.end());
for(int z=arr.size(),cx=0;cx<z;++cx){
for(int cy=cx+1;cy<cx+5&&cy<z;++cy){
insert(arr[cy].a-arr[cx].a,mdl(arr[cy].c-arr[cx].c),arr[cx].cnt+arr[cy].cnt);
}
}
}
ln-=ofst,rn-=ofst;
}
int main(){
stdcin.tie(nullptr)->sync_with_stdio(false);
stdcin>>T;
while(T--){
stdcin>>m>>p>>err;
err=(err+1)>>1;
ll ln=0,rn=p-1,mid;
for(int cx=0;cx<m;++cx)
stdcin>>pswz[cx].a>>pswz[cx].c;
for(int cx=0;cx<m;++cx)
pswz[cx].cnt=1;
while(rn-ln>6666)
guessX(ln,rn);
mid=(ln+rn)>>1;
for(ll cx=mid,cy=mid+1;true;--cx,++cy){
if(check(cx)){
stdcout<<(cx+p)%p<<stdendl;
break;
}
if(check(cy)){
stdcout<<(cy+p)%p<<std::endl;
break;
}
}
}
return 0;
}
