#include<bits/stdc++.h>
using namespace std;
const int maxn=2005,S1=200,S2=1000,S3=3,S4=5,S5=300,S6=9;
int T,n;
int p[10];
long long mod,err,nowL,nowR,ans;
long long a[maxn],c[maxn];
struct node{
	long long a,c,cnt;
	inline bool operator ==(node &p)const{
		return a==p.a;
	}
	inline bool operator <(node &p)const{
		return a<p.a;
	}
};
vector<node>V;
inline long long inc(long long x){
	return x>=mod? x-mod:x;
}
inline long long dec(long long x){
	return x<0? x+mod:x;
}
inline long long mul(long long x,long long y){
	return (x*y-(long long)((long double)x/mod*y)*mod+mod)%mod;
}
int check(long long X){
	X=(X%mod+mod)%mod;
	int flg=1;
	for(int i=1;i<=n;i++){
		long long val=dec(mul(a[i],X)-c[i]);
		flg&=(val<=err||val>=mod-err);
	}
	return flg;
}
mt19937_64 rnd(144441);
void addnode(long long a,long long c,long long cnt){
	V.push_back(node{a,c,cnt});
	if(err>mod/cnt/2||(nowR-nowL+1)>mod/a)
		return ;
	long long L=mul(nowL,a),R=mul(nowR,a),tmpL=c-cnt*err,tmpR=c+cnt*err;
	while(L>R)
		R+=mod;
	while(tmpL>R)
		tmpL-=mod,tmpR-=mod;
	while(tmpR<L)
		tmpL+=mod,tmpR+=mod;
	if(tmpL+mod>R&&tmpR-mod<L)
		nowL+=max(tmpL-L,0ll)/a,nowR-=max(R-tmpR,0ll)/a;
}
int main(){
	srand(time(0));
	scanf("%d",&T); 
	while(T--){
		scanf("%d%lld",&n,&mod),err=(mod/100+1)/2,nowL=0,nowR=mod-1;
		for(int i=1;i<=n;i++)
			scanf("%lld%lld",&a[i],&c[i]);
		while(nowR-nowL+1>S1){
			V.clear();
			long long delta=rnd()%mod;
			delta=0;
			nowL+=delta,nowR+=delta;
			if(nowR-nowL+1>mod/4)
				nowL=0,nowR=mod-1;
			for(int i=1;i<=S2;i++){
				long long nowA=0,nowC=0;
				for(int j=1;j<=S3;j++){
					int x=rnd()%n+1;
					while(1){
						int flg=0;
						for(int k=1;k<j;k++)
							if(p[k]==x)
								flg=1;
						if(flg==0)
							break;
						x=rnd()%n+1;
					}
					p[j]=x;
					long long aa=a[x],cc=inc(c[x]+mul(a[x],delta));
					if(rnd()&1)
						nowA=inc(nowA+aa),nowC=inc(nowC+cc);
					else nowA=dec(nowA-aa),nowC=dec(nowC-cc);
				}
				addnode(nowA,nowC,(long long)S3);
			}
			for(int i=1;i<=S4;i++){
				if(V.size()>S5)
					nth_element(V.begin(),V.begin()+S5,V.end()),V.resize(S5);
				sort(V.begin(),V.end()),V.erase(unique(V.begin(),V.end()),V.end());
				int rec=V.size();
				for(int j=0;j<rec;j++)
					for(int k=j+1;k<=j+S6&&k<rec;k++)
						addnode(V[k].a-V[j].a,dec(V[k].c-V[j].c),V[j].cnt+V[k].cnt);
			}
			nowL-=delta,nowR-=delta;
		}
		ans=0;
		for(long long i=nowL;i<=nowR;i++)
			if(check(i)){
				ans=i;
				break;
			}
		printf("%lld\n",(ans%mod+mod)%mod);
	}
	return 0;	
}