#include <bits/stdc++.h>
using namespace std;
const int MAXK = 60;
const int MAXT = 1E4 + 10;
const int LIM = 1E5 + 10;
namespace Pollard_Rho {
const int pr[] = {2, 3, 5, 7, 11, 23, 43, 79};
const int M = (1 << 8) - 1;
mt19937 RandEngine(chrono::steady_clock::now().time_since_epoch().count());
long long RandInt(long long L, long long R) {
  return uniform_int_distribution<long long>(L, R)(RandEngine);
}
vector<long long> Res;
long long Mx = 0;
long long gcd(long long a, long long b) {
  if (!a || !b) return a | b;
  int shift = __builtin_ctzll(a | b);
  b >>= __builtin_ctzll(b);
  while (a) {
    a >>= __builtin_ctzll(a);
    if (a < b) swap(a, b);
    a -= b;
  }
  return b << shift;
}
unsigned long long Mul(unsigned long long a, unsigned long long b,
                       unsigned long long P) {
  unsigned long long c =
      (long long)a * b -
      (long long)((unsigned long long)((long double)a * b / P)) * P;
  return (c + P) % P;
}
long long ksm(long long a, long long b, long long P) {
  long long ret = 1;
  for (; b; b >>= 1, a = Mul(a, a, P))
    if (b & 1) ret = Mul(ret, a, P);
  return ret;
}
bool Miller_Rabin(long long n) {
  if (n == 2 || n == 3 || n == 5 || n == 7 || n == 11 || n == 23 || n == 43 ||
      n == 79)
    return true;
  if (~n & 1) return false;
  for (int p : pr) {
    long long t = n - 1, c = 0;
    while (~t & 1) t >>= 1, ++c;
    long long pw = ksm(p, t, n);
    if (pw == 1) continue;
    bool f = (pw == n - 1);
    while (c) {
      pw = Mul(pw, pw, n);
      f |= (pw == n - 1);
      --c;
      if (pw == 1 && !f) return false;
    }
    if (pw != 1 || !f) return false;
  }
  return true;
}
long long Pollard_Rho(long long n) {
  int c = RandInt(1, n - 1);
  long long t = 1, x = 0, y = 0, q = 1;
  auto F = [=](long long x) { return (Mul(x, x, n) + c) % n; };
  for (int i = 2;; i <<= 1, y = x, q = 1) {
    for (int j = 1; j <= i; j++) {
      x = F(x);
      q = Mul(q, abs(x - y), n);
      if (!(j & M)) {
        if ((t = gcd(q, n)) > 1) break;
      }
    }
    if (t > 1 || ((t = gcd(q, n)) > 1)) break;
  }
  if (t == n) {
    t = 1;
    while (t == 1) x = F(x), t = gcd(abs(x - y), n);
  }
  return t;
}
void Factorize(long long n) {
  if (Miller_Rabin(n)) return Res.push_back(n), void();
  long long d = n;
  while (d == n) d = Pollard_Rho(n);
  Factorize(n / d);
  Factorize(d);
}
vector<long long> solve(long long n) {
  Res.clear();
  Factorize(n);
  return Res;
}
}  // namespace Pollard_Rho
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) return x = 1, y = 0, void();
  exgcd(b, a % b, y, x);
  y -= (a / b) * x;
}
int Ans[MAXT], tot;
long long dis[LIM];
priority_queue<pair<long long, int>, vector<pair<long long, int> >,
               greater<pair<long long, int> > >
    pq;
vector<long long> pr;
map<long long, int> M;
vector<pair<long long, int> > Q[MAXK];
void Dijkstra() {
  memset(dis, 0x3f, sizeof dis);
  dis[0] = 0;
  pq.emplace(0, 0);
  while (!pq.empty()) {
    auto x = pq.top();
    pq.pop();
    if (x.first != dis[x.second]) continue;
    for (long long p : pr) {
      long long v = (p + x.second) % pr[0];
      if (dis[v] <= x.first + p) continue;
      dis[v] = x.first + p;
      pq.emplace(dis[v], v);
    }
  }
}
int main() {
  int T, tst = 0;
  scanf("%d", &T);
  for (long long n, k; T; T--) {
    scanf("%lld%lld", &n, &k);
    if (!M.count(k)) M[k] = ++tot;
    int id = M[k];
    Q[id].emplace_back(n, ++tst);
  }
  for (auto pK : M) {
    int idx = pK.second;
    long long K = pK.first;
    if (K == 1) continue;
    pr = Pollard_Rho::solve(K);
    if (pr.size() == 1) {
      for (auto q : Q[idx]) Ans[q.second] = q.first % K == 0;
    } else if (pr.size() == 2) {
      for (auto q : Q[idx]) {
        long long x, y;
        exgcd(pr[0], pr[1], x, y);
        x = (x % pr[1] + pr[1]) % pr[1];
        long long fx = Pollard_Rho::Mul(x, q.first, pr[1]), fy;
        fy = (q.first - fx * pr[0]) / pr[1];
        assert(fx * pr[0] + fy * pr[1] == q.first);
        Ans[q.second] = fx >= 0 && fy >= 0;
      }
    } else {
      sort(pr.begin(), pr.end());
      Dijkstra();
      for (auto q : Q[idx]) Ans[q.second] = dis[q.first % pr[0]] <= q.first;
    }
  }
  for (int i = 1; i <= tst; i++) puts(Ans[i] ? "YES" : "NO");
}
