//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//~ #pragma GCC target ("avx2")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define shandom_ruffle random_shuffle

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax=5000*1007;

using ld=long double;

int n;
ll p;
ll o2;
pll tab[nax];

pll normuj(pll v)
{
	while(v.first<0)
	{
		v.first+=p;
		v.second+=p;
	}
	while(v.first>=p)
	{
		v.first-=p;
		v.second-=p;
	}
	return v;
}

inline ll mno(ll a, ll b)
{
	return (a*(__int128)b)%p;
}

ll pot(ll a, ll b)
{
	ll ret=1;
	while(b)
	{
		if (b&1)
			ret=mno(ret, a);
		a=mno(a, a);
		b>>=1;
	}
	return ret;
}

ll inv(ll v)
{
	return pot(v, p-2);
}

pll now[nax];
int nowr;

pll wek[nax];
int wekr;

vector<pair<ll,pll>> szuk(ll chce)
{
	wekr=0;
	ll ocel=inv(chce);
	for (int i=1; i<=n; i++)
		if (rand()%20)
			wek[wekr++]={mno(tab[i].first, ocel), tab[i].second};
	sort(wek, wek+wekr);
	int d=5;
	const int ogr=700;
	int outuj=0;
	for (int h=0; h<d; h++)
	{
		//~ if (wek[0].first<3000)
		//~ {
			//~ debug() << "faster " << h;
			//~ d=h;
			//~ break;
		//~ }
		nowr=0;
		for (int h1=0; h1+1<wekr; h1++)
		{
			for (int h2=h1+1; h2<wekr && h2<=h1+7; h2++)
			{
				ll x=wek[h2].first-wek[h1].first;
				ll y=wek[h2].second-wek[h1].second;
				if (!x)
					continue;
				if (y<0)
					y+=p;
				if (x<1000)
				{
					wek[0]={x, y};
					wekr=1;
					outuj=1;
					d=h+1;
					break;
				}
				now[nowr++]={x, y};
			}
			if (outuj)
				break;
		}
		if (outuj)
			break;
		if (nowr<ogr+50)
		{
			sort(now, now+nowr);
		}
		else
		{
			nth_element(now, now+ogr+20, now+nowr);
			sort(now, now+ogr+20);
		}
		wekr=0;
		for (int i=0; i<nowr && wekr<ogr && i<ogr+20; i++)
		{
			if (!i || now[i].first!=wek[wekr-1].first)
			{
				wek[wekr++]=now[i];
			}
		}
	}
	wekr=min(wekr, 1);
	for (int i=wekr-1; i; i--)
		if (wek[i].first*5>wek[0].first*4)
			wekr--;
	vector<pair<ll,pll>> ret;
	for (int h=0; h<wekr; h++)
	{
		ll x=wek[h].first;
		ll y=wek[h].second;
		pll prz{y-((p/600)<<d), y+((p/600)<<d)};
		ret.push_back({x, normuj(prz)});
	}
	return ret;
}

pll raz[nax];
int razr;
pll dwa[nax];
int dwar;

pll ret[nax];
int retr;

void przetnij()
{
	sort(dwa, dwa+dwar);
	if (razr==1 && raz[0].second-raz[0].first==p-1)
	{
		for (int i=0; i<dwar; i++)
			raz[i]=dwa[i];
		razr=dwar;
		return;
	}
	retr=0;
	int wskr=0;
	int wskd=0;
	while(wskr<razr && wskd<dwar)
	{
		pll x=raz[wskr];
		pll y=dwa[wskd];
		if (x.second<y.first)
		{
			wskr++;
			continue;
		}
		if (y.second<x.first)
		{
			wskd++;
			continue;
		}
		pll z={max(x.first, y.first), min(x.second, y.second)};
		if (z.first<=z.second)
			ret[retr++]=z;
		if (x.second<y.second)
			wskr++;
		else
			wskd++;
	}
	for (int i=0; i<retr; i++)
		raz[i]=ret[i];
	razr=retr;
}

void test()
{
	scanf("%d%lld", &n, &p);
	o2=(p+1)/2;
	for (int i=1; i<=n; i++)
		scanf("%lld%lld", &tab[i].first, &tab[i].second);
	while(1)
	{
		razr=1;
		raz[0]={0, p-1};
		ll mnoznik=1;
		while(1)
		{
			auto wezwsz=szuk(mnoznik);
			if (wezwsz[0].first>=nax/10)
				continue;
			for (auto wez : wezwsz)
			{
				//~ spent-=get_time();
				ll d=wez.first;
				if (d>=nax/10)
					continue;
				ll o=inv(d);
				ll a=wez.second.first;
				ll b=wez.second.second;
				dwar=0;
				for (int h=0; h<d; h++)
				{
					ll x=a+h;
					if (x>b)
						break;
					ll ile=(b-x)/d+1;
					static ll g;
					if (!h)
					{
						g=mno(x, o);
					}
					else
					{
						g+=o;
						if (g>=p)
							g-=p;
					}
					if (g+ile-1>p)
					{
						dwa[dwar++]={g, p-1};
						dwa[dwar++]={0, g+ile-1-p};
					}
					else
					{
						dwa[dwar++]={g, g+ile-1};
					}
				}
				//~ spent+=get_time();
				przetnij();
			}
			ll dobre=0;
			//~ for (pll i : raz)
			for (int i=0; i<razr; i++)
				dobre+=raz[i].second-raz[i].first+1;
			if (dobre<=50000)
			{
				break;
			}
			//~ debug() << imie(dobre) << imie(dobre/(double)p) << imie(raz.size());
			//~ debug() << mnoznik << " " << imie(dobre) << imie((raz.back().second-raz[0].first)/(double)p);
			//~ if ((raz.back().second-raz[0].first)*3<p*2 && (int)raz.size()<=100)
			const int lim=200;
			if (dobre*2<p && razr<=lim/2)
			//~ if ((int)raz.size()<=5000)
			{
				dwar=0;
				const ll mnoze=max(lim/razr, 2);
				//~ const ll mnoze=2+(rand()&1);
				const ll oo=inv(mnoze);
				mnoznik=mno(mnoznik, oo);
				for (int hh=0; hh<razr; hh++)
				{
					pll i=raz[hh];
					ll a=i.first;
					ll b=i.second;
					for (int h=0; h<mnoze; h++)
					{
						ll x=a+h;
						if (x>b)
							break;
						ll ile=(b-x)/mnoze+1;
						static ll g;
						if (!h)
						{
							g=mno(x, oo);
						}
						else
						{
							g+=oo;
							if (g>=p)
								g-=p;
						}
						if (g+ile-1>p)
						{
							dwa[dwar++]={g, p-1};
							dwa[dwar++]={0, g+ile-1-p};
						}
						else
						{
							dwa[dwar++]={g, g+ile-1};
						}
					}
				}
				sort(dwa, dwa+dwar);
				for (int i=0; i<dwar; i++)
					raz[i]=dwa[i];
				razr=dwar;
			}
		}
		ll pam=inv(mnoznik);
		//~ printf("%lld\n", mno(raz[0].first, inv(mnoznik)));
		for (int hh=0; hh<razr; hh++)
		{
			pll h=raz[hh];
			for (ll x=h.first; x<=h.second; x++)
			{
				//~ ll w=mno(x, pam);
				ll w=x*(__int128)pam%p;
				int ok=1;
				for (int i=1; i<=n; i++)
				{
					//~ ll y=mno(tab[i].first, w)-tab[i].second;
					ll y=tab[i].first*(__int128)w%p;
					y-=tab[i].second;
					y%=p;
					if (y<0)
						y+=p;
					if (y>p/2)
						y-=p;
					if (abs(y)>p/200)
					{
						ok=0;
						break;
					}
				}
				if (ok)
				{
					printf("%lld\n", w);
					return;
				}
			}
		}
		debug() << "error";
	}
}

int main()
{
	srand(time(0));
	int t;
	scanf("%d", &t);
	while(t--)
		test();
	return 0;
}