#include <bits/stdc++.h>
using namespace std;
int t, cnt, ans, pr[32000010], tot;
bool p[32000010], an[100010];
long long f[100010], inf = 1e18 + 7, d[100];
struct qu {
  long long n, m;
  int id;
  bool operator<(qu const &a) const { return m < a.m; }
} q[100010];
struct node {
  int s;
  long long v;
  node(int _s = 0, long long _v = 0) { s = _s, v = _v; }
  bool operator<(node const &a) const { return v > a.v; }
};
priority_queue<node> qe;
long long mul(long long a, long long b, long long c) {
  a %= c;
  b %= c;
  long long k = 0;
  while (b) {
    if (b & 1) k = (k + a) % c;
    a = 2 * a % c;
    b >>= 1;
  }
  return k;
}
long long pw(long long i, long long k, long long mm) {
  long long a = 1;
  while (k) {
    if (k & 1) a = mul(a, i, mm);
    i = mul(i, i, mm);
    k >>= 1;
  }
  return a;
}
void solve(long long mi) {
  int i, s, a, b, k;
  long long vv = mi;
  node j;
  for (i = 1, cnt = 0; i <= tot && pr[i] * pr[i] <= vv; i++)
    if (!(vv % pr[i])) {
      while (!(vv % pr[i])) vv /= pr[i];
      d[++cnt] = pr[i];
    }
  if (vv > 1) d[++cnt] = vv;
  if (cnt < 3) return;
  for (i = 0; i < d[1]; i++) f[i] = inf;
  f[0] = 0;
  qe.push(node(0, 0));
  while (!qe.empty()) {
    j = qe.top();
    qe.pop();
    if (j.v > f[s = j.s]) continue;
    for (i = 2; i <= cnt; i++) {
      k = (s + d[i]) % d[1];
      if (f[k] > f[s] + d[i]) qe.push(node(k, f[k] = f[s] + d[i]));
    }
  }
}
int main() {
  int i, s, a, b;
  long long x, y, c, j, k;
  for (i = 2; i < 32000010; i++) {
    if (!p[i]) pr[++tot] = i;
    for (s = 1; s <= tot && i * pr[s] < 32000010; s++) {
      p[i * pr[s]] = 1;
      if (!(i % pr[s])) break;
    }
  }
  scanf("%d", &t);
  for (i = 1; i <= t; i++) scanf("%I64d%I64d", &q[i].n, &q[i].m), q[i].id = i;
  sort(q + 1, q + 1 + t);
  for (i = 1; i <= t; i = s) {
    solve(q[i].m);
    s = i;
    while (s <= t && q[s].m == q[i].m) {
      if (!cnt) an[q[s].id] = 0;
      if (cnt == 1) an[q[s].id] = !(q[s].n % d[1]);
      if (cnt == 2) {
        k = mul(q[s].n, j = pw(d[2], d[1] - 2, d[1]), d[1]);
        k = ((k % d[1]) + d[1]) % d[1];
        an[q[s].id] = (k <= (q[s].n / d[2]));
      }
      if (cnt >= 3) an[q[s].id] = (q[s].n >= f[q[s].n % d[1]]);
      s++;
    }
  }
  for (i = 1; i <= t; i++) {
    if (an[i])
      printf("YES\n");
    else
      printf("NO\n");
  }
  return 0;
}
