//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define i128 __int128_t
void die(string S){puts(S.c_str());exit(0);}
using range=pair<i128,i128>;
i128 p;
struct equation
{
	i128 a,c,err;
	equation(){}
	equation(i128 _a,i128 _c,i128 _err):a(_a),c(_c),err(_err){}
	bool operator <(equation b){return a<b.a;}
	equation operator +(equation b){return equation((a+b.a)%p,(c+b.c)%p,err+b.err);}
	equation operator -(equation b){return equation((a+p-b.a)%p,(c+p-b.c)%p,err+b.err);}
};
inline bool check(vector<equation> ve)
{
	for(auto E:ve) if(E.a!=1) return 0;
	return 1;
}
inline int sp(range R)
{
	return R.first>R.second;
}
inline range merge(range a,range b)
{
	if(!a.first&&a.second==p-1) return b;
	if(!b.first&&b.second==p-1) return a;
	assert((a.second-a.first+p)%p<p/2);
	assert((b.second-b.first+p)%p<p/2);
	if(sp(a)&&!sp(b)) swap(a,b);
	if(sp(a)&&sp(b)) return range(max(a.first,b.first),min(a.second,b.second));
	if(!sp(a)&&!sp(b)) return range(max(a.first,b.first),min(a.second,b.second));
	if(a.second>=b.first)
		return range(max(b.first,a.first),a.second);
	return range(a.first,min(a.second,b.second));
}
vector<equation> evolve(vector<equation> ve)
{
	const int limit=100;
	srt(ve);
	vector<equation> res;
	int p=-1;
	for(int i=0;i<sz(ve);i++)
	{
		while(p+1<sz(ve)&&ve[p+1].a<ve[i].a) p++;
		if(~p) res.pb(ve[i]-ve[p]);
	}
	for(auto E:ve) res.pb(E);
	srt(res);
	while(sz(res)>limit) res.pop_back();
	return res;
}
void solve()
{
	vector<equation> ve;
	int n;
	cin>>n;
	ll _p;
	cin>>_p;
	p=_p;
	ll err;
	cin>>err;
	err=(err+1)/2;
	for(int i=0;i<n;i++)
	{
		ll a,b;
		cin>>a>>b;
		ve.pb(a,b,err);
	}
	vector<equation> history=ve;
	int round=0;
	while(!check(ve))
	{
		round++;
		ve=evolve(ve);
		for(auto E:ve) history.pb(E);
	}
	range R(0,p-1);
	for(auto E:ve)
	{
		range nR((E.c-E.err+p)%p,(E.c+E.err)%p);
		R=merge(R,nR);
	}
	for(int i=0;i<10;i++)
	{
		for(auto E:history)
		{
			i128 Lb=E.a*R.first;
			i128 Rb=E.a*(R.second<R.first?(R.second+p):R.second);
			if(Lb/p==Rb/p)
			{
				i128 dest=(Lb/p*p)+E.c;
				i128 Err=E.err;
				Lb=max(Lb,dest-Err);
				Rb=min(Rb,dest+Err);
				Lb=(Lb+E.a-1)/E.a;
				Rb=Rb/E.a;
				if(Lb>=p) Lb-=p;
				if(Rb>=p) Rb-=p;
				R=range(Lb,Rb);
			}
			else if(Lb/p+1==Rb/p)
			{
				i128 dest=(Lb/p*p)+E.c;
				i128 Err=E.err;
				if(dest+Err<Lb||dest+p-Err>Rb)
				{
					if(dest+Err<Lb) dest+=p;
					Lb=max(Lb,dest-Err);
					Rb=min(Rb,dest+Err);
					Lb=(Lb+E.a-1)/E.a;
					Rb=Rb/E.a;
					if(Lb>=p) Lb-=p;
					if(Rb>=p) Rb-=p;
					R=range(Lb,Rb);
				}
			}
		}
	}
	cout<<(ll)(R.first)<<'\n';
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
		solve();
	return 0;
}