#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 3e5 + 5;
int T, p[2000000], cnt, m, edgenum, Head[N], Next[M], vet[M];
bool isnp[32000001], vis[N], ans[N];
long long n, k, K[55], d[20], val[M], dis[N], X, Y;
vector<pair<long long, int> > vec[55];
priority_queue<pair<long long, int>, vector<pair<long long, int> >,
               greater<pair<long long, int> > >
    que;
inline void add(int u, int v, long long w) {
  Next[++edgenum] = Head[u];
  Head[u] = edgenum;
  vet[edgenum] = v;
  val[edgenum] = w;
}
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x), y -= a / b * x;
}
int main() {
  for (int i = 2; i <= 32000000; i++) {
    if (!isnp[i]) p[++cnt] = i;
    for (int j = 1; j <= cnt && i * p[j] <= 32000000; j++) {
      isnp[i * p[j]] = 1;
      if (!(i % p[j])) break;
    }
  }
  cin >> T;
  for (int i = 1; i <= T; i++) {
    scanf("%lld%lld", &n, &k);
    int id;
    for (id = 1; id <= m; id++)
      if (K[id] == k) break;
    if (id > m) K[++m] = k;
    vec[id].push_back(pair<long long, int>(n, i));
  }
  for (int i = 1; i <= m; i++) {
    long long _ = K[i];
    int dcnt = 0;
    for (int j = 1; 1ll * p[j] * p[j] <= K[i]; j++)
      if (!(_ % p[j])) {
        d[++dcnt] = p[j];
        while (!(_ % p[j])) _ /= p[j];
      }
    if (_ > 1) d[++dcnt] = _;
    if (!dcnt)
      continue;
    else if (dcnt == 1)
      for (auto q : vec[i]) ans[q.second] = !(q.first % d[1]);
    else if (dcnt == 2) {
      exgcd(d[1], d[2], X, Y);
      for (auto q : vec[i])
        ans[q.second] =
            ((__int128)X * q.first % d[2] + d[2]) % d[2] * d[1] +
                ((__int128)Y * q.first % d[1] + d[1]) % d[1] * d[2] <=
            q.first;
    } else {
      edgenum = 0;
      for (int i = 0; i < d[1]; i++)
        Head[i] = vis[i] = 0, dis[i] = (long long)1e18 + 1;
      for (int i = 2; i <= dcnt; i++)
        for (int j = 0; j < d[1]; j++) add(j, (j + d[i]) % d[1], d[i]);
      dis[0] = 0, que.push(pair<long long, int>(0, 0));
      while (!que.empty()) {
        int u = que.top().second;
        que.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int e = Head[u]; e; e = Next[e]) {
          int v = vet[e];
          long long w = val[e];
          if (dis[v] > dis[u] + w)
            dis[v] = dis[u] + w, que.push(pair<long long, int>(dis[v], v));
        }
      }
      for (auto q : vec[i]) ans[q.second] = q.first >= dis[q.first % d[1]];
    }
  }
  for (int i = 1; i <= T; i++) puts(ans[i] ? "YES" : "NO");
  return 0;
}
