#include <bits/stdc++.h>
int t;
struct item {
  int id;
  long long n, k;
  bool operator<(const item& it) const { return k < it.k; }
} items[10010];
bool ans[10010];
long long ps[100];
int pc;
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)
    x = 1, y = 0;
  else
    exgcd(b, a % b, y, x), y -= a / b * x;
}
long long rnd() {
  long long x = rand();
  x = x << 15 ^ rand();
  return x << 15 ^ rand();
}
unsigned long long mul(unsigned long long a, unsigned long long b,
                       unsigned long long p) {
  unsigned long long c = 0;
  for (; b; b >>= 13) (c += a * (b & 8191)) %= p, a = (a << 13) % p;
  return c;
}
unsigned long long pw(unsigned long long a, unsigned long long n,
                      unsigned long long p) {
  unsigned long long b = 1;
  for (; n; n >>= 1) n % 2 ? b = mul(b, a, p) : 1, a = mul(a, a, p);
  return b;
}
bool isp(long long x) {
  if (x < 4) return 1;
  if (x % 2 == 0) return 0;
  if (x == 46856248255981ll) return 0;
  const int a[5] = {2, 3, 7, 61, 24251};
  for (int i = 0; i < 5 && a[i] < x; i++) {
    long long y = x - 1, t, u;
    while (y % 2 == 0) y /= 2;
    for (t = pw(a[i], y, x); y < x; y *= 2, t = u)
      if ((u = mul(t, t, x)) == 1 && t != 1 && t != x - 1) return 0;
    if (t != 1) return 0;
  }
  return 1;
}
void fact(long long n) {
  for (; n % 2 == 0; n /= 2) ps[pc++] = 2;
  if (n == 1) return;
  if (isp(n)) {
    ps[pc++] = n;
    return;
  }
  for (long long x = rnd() % n, y = x, z;; x = y = rnd() % n) {
    z = rnd() % (n - 1) + 1;
    do {
      x = (mul(x, x, n) + z) % n;
      y = (mul(y, y, n) + z) % n;
      y = (mul(y, y, n) + z) % n;
      long long g = gcd(x > y ? x - y : y - x, n);
      if (g > 1 && g < n) {
        fact(g);
        fact(n / g);
        return;
      }
    } while (x != y);
  }
}
struct qitem {
  int v;
  long long d;
  bool operator<(const qitem& it) const { return d > it.d; }
};
long long dis[100010];
bool vis[100010];
void calc_sp() {
  for (int i = 0; i < ps[0]; i++) vis[i] = 0;
  std::priority_queue<qitem> Q;
  Q.push((qitem){0, 0});
  while (!Q.empty()) {
    qitem it = Q.top();
    Q.pop();
    if (vis[it.v]) continue;
    vis[it.v] = 1;
    dis[it.v] = it.d;
    for (int j = 0; j < pc; j++) {
      int t = (it.v + ps[j]) % ps[0];
      if (!vis[t]) Q.push((qitem){t, it.d + ps[j]});
    }
  }
}
int main() {
  srand(time(0));
  scanf("%d", &t);
  for (int i = 0; i < t; i++) {
    scanf("%lld%lld", &items[i].n, &items[i].k);
    items[i].id = i;
  }
  std::sort(items, items + t);
  for (int tl = 0, tr = 0; tl < t; tl = tr) {
    long long k = items[tl].k;
    pc = 0;
    fact(k);
    std::sort(ps, ps + pc);
    pc = std::unique(ps, ps + pc) - ps;
    if (pc > 2) calc_sp();
    for (; tr < t && items[tr].k == k; tr++) {
      int id = items[tr].id;
      long long n = items[tr].n;
      if (!pc)
        ans[id] = 0;
      else if (pc == 1)
        ans[id] = n % ps[0] == 0;
      else if (pc == 2) {
        long long x, y;
        exgcd(ps[0], ps[1], x, y);
        x = (x + ps[1]) % ps[1];
        x = mul(x, n % ps[1], ps[1]);
        ans[id] = ps[0] * x <= n;
      } else
        ans[id] = vis[n % ps[0]] && dis[n % ps[0]] <= n;
    }
  }
  for (int i = 0; i < t; i++) puts(ans[i] ? "YES" : "NO");
}
