#include <bits/stdc++.h>
using namespace std;
map<long long, vector<pair<long long, int>>> mapchik;
const long long INF = (long long)2e18;
const int M = (int)35e6;
const int PSZ = (int)3e6;
bool p[M];
int pr[PSZ];
int prSz;
const int N = (int)1e5 + 10;
bool ANS[N];
long long dist[N];
long long euclid(long long x, long long y, long long &k, long long &l) {
  if (y == 0) {
    k = 1;
    l = 0;
    return x;
  }
  long long g = euclid(y, x % y, l, k);
  l -= k * (x / y);
  return g;
}
vector<long long> factorize(long long x) {
  vector<long long> res;
  for (int i = 0; i < prSz; i++) {
    if (x % pr[i]) continue;
    res.push_back(pr[i]);
    while (x % pr[i] == 0) x /= pr[i];
  }
  if (x > 1) res.push_back(x);
  return res;
}
void solve(long long k, vector<pair<long long, int>> queries) {
  vector<long long> a = factorize(k);
  int n = (int)a.size();
  if (n == 0) {
    return;
  } else if (n == 1) {
    for (pair<long long, int> q : queries) {
      ANS[q.second] = q.first % a[0] == 0;
    }
    return;
  } else if (n == 2) {
    long long r = 0, s = 0;
    if (euclid(a[0], a[1], r, s) != 1) throw;
    s %= a[0];
    if (s < 0) s += a[0];
    for (pair<long long, int> q : queries) {
      long long z = ((s * (q.first % a[0])) % a[0]) * a[1];
      ANS[q.second] = z <= q.first;
    }
    return;
  }
  int m = a[0];
  for (int i = 0; i < m; i++) dist[i] = INF;
  dist[0] = 0;
  set<pair<long long, int>> setik;
  for (int i = 0; i < m; i++) setik.insert(make_pair(dist[i], i));
  while (!setik.empty()) {
    int v = setik.begin()->second;
    setik.erase(setik.begin());
    for (int i = 1; i < n; i++) {
      int u = (v + a[i]) % m;
      long long w = dist[v] + a[i];
      if (w >= dist[u]) continue;
      setik.erase(make_pair(dist[u], u));
      dist[u] = w;
      setik.insert(make_pair(dist[u], u));
    }
  }
  for (pair<long long, int> q : queries) {
    ANS[q.second] = dist[q.first % m] <= q.first;
  }
}
int main() {
  for (int i = 2; i < M; i++) p[i] = 1;
  for (int x = 2; x < M; x++) {
    if (!p[x]) continue;
    pr[prSz++] = x;
    for (int y = 2 * x; y < M; y += x) p[y] = 0;
  }
  int t;
  scanf("%d", &t);
  for (int i = 0; i < t; i++) {
    long long n, k;
    scanf("%lld%lld", &n, &k);
    mapchik[k].push_back(make_pair(n, i));
  }
  for (auto it : mapchik) {
    solve(it.first, it.second);
  }
  for (int i = 0; i < t; i++)
    if (ANS[i])
      printf("YES\n");
    else
      printf("NO\n");
  return 0;
}
