#include <bits/stdc++.h>
#define int long long
#define i128 __int128

using namespace std;

const int QQQ = 10000, SQ = 20, A = 100000;
int Q;
struct QQ
{
	int n, m;
	int id;
	bool operator < (const QQ &t) const
	{
		return m < t.m;
	}
}q[QQQ + 5];

void init()
{
	scanf("%lld", &Q);
	for(int i = 1; i <= Q; i++)
	{
		int n, m;
		scanf("%lld %lld", &n, &m);
		q[i] = {n, m, i};
	}
}

void exgcd(int a, int b, int &x, int &y)
{
	if(b == 0)
	{
		x = 1, y = 0;
		return;
	}
	exgcd(b, a % b, x, y);
	int t = x;
	x = y;
	y = t - a / b * y;
}

struct Edge
{
	int v, w, nxt;
}edge[1500005];
int head[100005], cnte;
void adde(int u, int v, int w)
{
	edge[++cnte] = {v, w, head[u]};
	head[u] = cnte;
}

int dv[SQ + 5], cntd;

void bld()
{
	for(int u = 0; u < dv[1]; u++)
	{
		for(int i = 2; i <= cntd; i++)
		{
			adde(u, (u + dv[i]) % dv[1], dv[i]);
		}
	}
}

int dis[100005];
bool inq[100005];
void spfa(int s)
{
	queue <int> qu;
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	inq[s] = 1;
	qu.push(s);
	while(qu.size())
	{
		int u = qu.front();
		qu.pop();
		inq[u] = 0;
		for(int i = head[u]; i; i = edge[i].nxt)
		{
			int v = edge[i].v;
			if(dis[v] > dis[u] + edge[i].w)
			{
				dis[v] = dis[u] + edge[i].w;
				if(!inq[v])
				{
					qu.push(v);
					inq[v] = 1;
				}
			}
		}
	}
}

bool vis[32000005];
int pri[2000005], cntp;
void eular()
{
	for(int i = 2; i <= 32000000; i++)
	{
		if(!vis[i])
		{
			pri[++cntp] = i;
		}
		for(int j = 1; j <= cntp && i <= 32000000 / pri[j]; j++)
		{
			vis[i * pri[j]] = 1;
			if(i % pri[j] == 0)
			{
				break;
			}
		}
	}
}

bool ans[QQQ + 5];
void solve()
{
	eular();
	sort(q + 1, q + Q + 1);
	for(int s = 1; s <= Q; s++)
	{
		int n = q[s].n, m = q[s].m;
		if(s == 1 || m != q[s - 1].m)
		{
			for(int u = 0; u < dv[1]; u++)
			{
				head[u] = 0;
			}
			cnte = 0;
			cntd = 0;
			
			int t = m;
			for(int i = 1; i <= cntp && pri[i] * pri[i] <= t; i++)
			{
				if(t % pri[i] == 0)
				{
					dv[++cntd] = pri[i];
					while(t % pri[i] == 0)
					{
						t /= pri[i];
					}
				}
			}
			if(t > 1)
			{
				dv[++cntd] = t;
			}
//			printf("%d\n", cntd);
//			printf("%lld %lld %lld\n", n, m, cntd);
//			for(int i = 1; i <= cntd; i++)
//			{
//				printf("%lld ", dv[i]);
//			}
//			printf("\n");
			
			if(cntd > 2)
			{
				bld();
				spfa(0);
			}
		}
		if(m == 1)
		{
			ans[q[s].id] = 0;
			continue;
		}
		else if(cntd == 1)
		{
			if(n % dv[1] == 0)
			{
				ans[q[s].id] = 1;
			}
			continue;
		}
		else if(cntd == 2)
		{
			int a = dv[1], b = dv[2], xx, yy;
			exgcd(a, b, xx, yy);
			i128 x, y;
			x = (i128)xx * n;
			y = (i128)yy * n;
			if(n % a == 0 || n % b == 0)
			{
				ans[q[s].id] = 1;
				continue;
			}
			i128 sk = (int)floor(x * 1.0 / b);
			x -= sk * b;
			y += sk * a;
			if(y > 0)
			{
				ans[q[s].id] = 1;
			}
			continue;
//			ans[q[s].id] = 1;
//			continue;
		}
		if(dis[n % dv[1]] <= n)
		{
			ans[q[s].id] = 1;
		}
	}
	for(int i = 1; i <= Q; i++)
	{
		if(ans[i])
		{
			printf("YES\n");
		}
		else
		{
			printf("NO\n");
		}
	}
}

signed main()
{
//	freopen("gen.in", "r", stdin);
//	freopen("video114.out", "w", stdout);
	init();
	solve();
	return 0;
}

第十组数据，k 全部为质数，t=10000 然后 TLE

理论上计算量为 50*2000000