#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 5;
const int M = 1e6 + 5;
struct node {
  long long n, k;
  int pos;
} q[N];
struct data {
  int id;
  long long d;
  bool operator<(data r) const { return d > r.d; }
};
priority_queue<data> g;
long long dis[M];
int ans[N], vis[M], p[M];
int tot, cnt;
bool cmp(node a, node b) { return a.k < b.k; }
long long abs1(long long x) { return x < 0 ? -x : x; }
long long gcd(long long x, long long y) { return !y ? x : gcd(y, x % y); }
inline long long mul(long long x, long long p, long long mo) {
  long long ret = 0;
  for (; p; p >>= 1, x = (x + x) % mo)
    if (p & 1) ret = (ret + x) % mo;
  return ret;
}
inline long long pow(long long x, long long p, long long mo) {
  long long ret = 1;
  for (; p; p >>= 1, x = mul(x, x, mo))
    if (p & 1) ret = mul(ret, x, mo);
  return ret;
}
inline bool Mill(long long x) {
  if (x < 2) return 0;
  int s = 0;
  long long z = x;
  --x;
  while (!(x & 1)) x >>= 1, ++s;
  for (int i = 0; i < 10; ++i) {
    long long k = (rand() * rand()) % z;
    while (!k) k = (rand() * rand()) % z;
    k = pow(k, x, z);
    long long pre = k;
    for (int j = 0; j < s; ++j) {
      k = mul(k, k, z);
      if (k == 1 && pre != 1 && pre != z - 1) return 0;
      pre = k;
    }
    if (k != 1) return 0;
  }
  return 1;
}
inline long long rho(long long x) {
  int l = 1, r = 2;
  long long x0 = (rand() * rand()) % x, y = x0, c = (rand() * rand()) % x + 1;
  while (1) {
    ++l;
    x0 = (mul(x0, x0, x) + c) % x;
    long long now = gcd(abs1(x0 - y), x);
    if (now != 1 && now != x) return now;
    if (x0 == y) return x;
    if (l == r) r <<= 1, y = x0;
  }
}
inline void divi(long long x) {
  if (x == 1) return;
  if (Mill(x)) {
    p[++cnt] = x;
    return;
  }
  long long d = rho(x);
  divi(x / d);
  divi(d);
}
inline void dij() {
  dis[0] = 0, g.push((data){0, 0});
  while (!g.empty()) {
    data x = g.top();
    g.pop();
    if (vis[x.id]) continue;
    vis[x.id] = 1;
    for (int i = 2; i <= cnt; ++i) {
      int v = (x.id + p[i]) % p[1];
      if (dis[v] > dis[x.id] + p[i]) {
        dis[v] = dis[x.id] + p[i];
        g.push((data){v, dis[v]});
      }
    }
  }
}
int main() {
  int t;
  scanf("%d", &t);
  for (int i = 1; i <= t; ++i)
    scanf("%I64d%I64d", &q[i].n, &q[i].k), q[i].pos = i;
  sort(q + 1, q + t + 1, cmp);
  for (int i = 1; i <= t; ++i) {
    if (q[i].k == q[i - 1].k) {
      if (!cnt) {
        ans[q[i].pos] = 0;
        continue;
      }
      if (cnt == 1) {
        if (q[i].n % q[i].k == 0)
          ans[q[i].pos] = 1;
        else
          ans[q[i].pos] = 0;
        continue;
      }
      if (cnt == 2) {
        long long b = q[i].n % p[1] *
                      pow((long long)p[2], p[1] - 2, (long long)p[1]) % p[1];
        if (b * p[2] <= q[i].n)
          ans[q[i].pos] = 1;
        else
          ans[q[i].pos] = 0;
        continue;
      }
      ans[q[i].pos] = dis[q[i].n % (long long)p[1]] <= q[i].n;
      continue;
    }
    cnt = 0;
    divi(q[i].k);
    sort(p + 1, p + cnt + 1);
    cnt = unique(p + 1, p + cnt + 1) - p - 1;
    if (!cnt) {
      ans[q[i].pos] = 0;
      continue;
    }
    if (cnt == 1) {
      if (q[i].n % q[i].k == 0)
        ans[q[i].pos] = 1;
      else
        ans[q[i].pos] = 0;
      continue;
    }
    if (cnt == 2) {
      long long b = q[i].n % p[1] *
                    pow((long long)p[2], p[1] - 2, (long long)p[1]) % p[1];
      if (b * p[2] <= q[i].n)
        ans[q[i].pos] = 1;
      else
        ans[q[i].pos] = 0;
      continue;
    }
    for (int j = 0; j < p[1]; ++j) vis[j] = 0, dis[j] = 1e18;
    dij();
    ans[q[i].pos] = dis[q[i].n % p[1]] <= q[i].n;
  }
  for (int i = 1; i <= t; ++i)
    if (ans[i])
      puts("YES");
    else
      puts("NO");
  return 0;
}
