#include <bits/stdc++.h>
using namespace std;
template <typename TP>
inline void read(TP &ret) {
  TP x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  ret = (TP)x * f;
}
int t;
struct node {
  long long n, k;
  int id;
  bool operator<(const node &other) const { return k < other.k; }
} a[10010];
long long bas[5] = {2, 3, 7, 61, 24251};
long long gcd(long long x, long long y) {
  if (!y) {
    return x;
  }
  return gcd(y, x % y);
}
long long add(long long a, long long b, long long mod) {
  return (a + b > mod) ? a + b - mod : a + b;
}
long long ksc(long long a, long long b, long long mod) {
  long long sum = 0;
  while (b) {
    if (b & 1) {
      sum = add(sum, a, mod);
      b--;
    }
    a = add(a, a, mod);
    b >>= 1;
  }
  return sum % mod;
}
long long ksm(long long a, long long b, long long mod) {
  long long product = 1;
  while (b) {
    if (b & 1) {
      product = ksc(product, a, mod);
      b--;
    }
    a = ksc(a, a, mod);
    b >>= 1;
  }
  return product % mod;
}
bool Miller_Rabin(long long x, long long b) {
  if (ksm(b, x - 1, x) != 1) return 0;
  long long k = x - 1;
  while (!(k & 1)) {
    k >>= 1;
    long long d = ksm(b, k, x);
    if (d != 1 && d != x - 1) return 0;
    if (d == x - 1) return 1;
  }
  return 1;
}
bool Miller_Rabin(long long x) {
  if (x < 2 || x == 46856248255981) return 0;
  for (int i = 0; i < 5; i++) {
    if (x == bas[i]) return 1;
  }
  for (int i = 0; i < 5; i++) {
    if (!Miller_Rabin(x, bas[i])) return 0;
  }
  return 1;
}
long long Mandelbrot(long long x, long long c, long long p) {
  return (ksc(x, x, p) + c) % p;
}
long long Pollard_Rho(long long x) {
  long long s, t, c = 1ll * rand() % (x - 1) + 1;
  s = t = 0;
  long long val = 1;
  int goal = 1;
  for (;; goal <<= 1, s = t, val = 1) {
    for (int i = 1; i <= goal; i++) {
      t = Mandelbrot(t, c, x);
      val = ksc(val, abs(t - s), x);
      if (!(i % 127)) {
        long long g = gcd(val, x);
        if (g > 1) return g;
      }
    }
    long long g = gcd(val, x);
    if (g > 1) return g;
  }
}
vector<long long> fac;
long long min_factor;
void divide(long long x) {
  if (x < 2) {
    return;
  }
  if (Miller_Rabin(x)) {
    min_factor = min(min_factor, x);
    fac.push_back(x);
    return;
  }
  long long p = x;
  while (p >= x) p = Pollard_Rho(x);
  while (!(x % p)) {
    x /= p;
  }
  divide(x);
  divide(p);
}
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = exgcd(b, a % b, x, y);
  long long res = x;
  x = y;
  y = res - a / b * y;
  return d;
}
long long dis[200020];
bool vis[200020];
queue<int> q;
void spfa(long long mod) {
  for (int i = 0; i < mod; i++) {
    dis[i] = 1000000000000000000ll;
    vis[i] = 0;
  }
  dis[0] = 0;
  q.push(0);
  vis[0] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for (int i = 1; i < fac.size(); i++) {
      int v = (u + fac[i]) % mod;
      if (dis[v] > dis[u] + fac[i]) {
        dis[v] = dis[u] + fac[i];
        if (!vis[v]) {
          q.push(v);
          vis[v] = 1;
        }
      }
    }
  }
}
bool ans[10010];
int main() {
  srand(time(NULL));
  read(t);
  for (int i = 1; i <= t; i++) {
    read(a[i].n), read(a[i].k);
    a[i].id = i;
  }
  sort(a + 1, a + t + 1);
  for (int i = 1; i <= t; i++) {
    int now = i;
    while (now < t && a[now + 1].k == a[i].k) now++;
    if (a[i].k == 1) {
      i = now;
      continue;
    }
    fac.clear();
    min_factor = 1000000000000000000ll;
    divide(a[i].k);
    sort(fac.begin(), fac.end());
    if (fac.size() == 1) {
      for (int j = i; j <= now; j++) {
        if (!(a[j].n % fac[0])) ans[a[j].id] = 1;
      }
      i = now;
      continue;
    }
    if (fac.size() == 2) {
      long long x, y;
      long long g = exgcd(fac[0], fac[1], x, y);
      long long b = fac[1] / g;
      x = add(x, b, b);
      for (int j = i; j <= now; j++) {
        if (!(a[j].n % g)) {
          long long dx = x, dy = y;
          dx = ksc(dx, a[j].n / g, b);
          dy = (a[j].n - fac[0] * dx) / fac[1];
          if (dy >= 0) ans[a[j].id] = 1;
        }
      }
      i = now;
      continue;
    }
    spfa(min_factor);
    for (int j = i; j <= now; j++) {
      if (dis[a[j].n % min_factor] <= a[j].n) ans[a[j].id] = 1;
    }
    i = now;
  }
  for (int i = 1; i <= t; i++) {
    printf("%s\n", ans[i] ? "YES" : "NO");
  }
}
