#include <bits/stdc++.h>
using namespace std;
const long long maxn = 100010, inf = 1e9;
map<long long, long long> mp;
struct poi {
  long long x;
  long long dis;
};
priority_queue<poi> q;
bool operator<(poi a, poi b) { return a.dis > b.dis; }
struct edge {
  long long too;
  long long dis;
  long long pre;
} e[maxn * 15];
struct que {
  long long pos;
  long long w;
};
vector<que> v[maxn];
long long n, T, tot, K, tott, pcnt;
long long last[maxn], ans[maxn], prime[10000000];
long long dist[maxn], pri[maxn], pos[maxn];
bool vis[32000000];
template <typename T>
inline void read(T &k) {
  long long f = 1;
  k = 0;
  char c = getchar();
  while (c < '0' || c > '9') c == '-' && (f = -1), c = getchar();
  while (c <= '9' && c >= '0') k = k * 10 + c - '0', c = getchar();
  k *= f;
}
inline long long power(long long a, long long b, long long mod) {
  long long ans = 1;
  for (; b; b >>= 1, a = 1ll * a * a % mod)
    if (b & 1) ans = 1ll * a * ans % mod;
  return ans;
}
inline void add(long long x, long long y, long long z) {
  e[++tot] = (edge){y, z, last[x]};
  last[x] = tot;
}
inline void dij(long long s) {
  memset(dist, 0x3f, sizeof(dist));
  dist[s] = 0;
  q.push((poi){s, dist[s]});
  while (!q.empty()) {
    poi now = q.top();
    q.pop();
    if (now.dis != dist[now.x]) continue;
    for (long long i = last[now.x], too; i; i = e[i].pre)
      if (dist[too = e[i].too] > dist[now.x] + e[i].dis) {
        dist[too] = dist[now.x] + e[i].dis;
        q.push((poi){too, dist[too]});
      }
  }
}
inline void getpri(long long n) {
  for (long long i = 2; i <= n; i++) {
    if (!vis[i]) prime[++pcnt] = i;
    for (long long j = 1; prime[j] * i <= n; j++) {
      vis[prime[j] * i] = 1;
      if (i % prime[j] == 0) break;
    }
  }
}
signed main() {
  read(T);
  getpri(sqrt(1e15));
  for (long long i = 1; i <= T; i++) {
    read(n);
    read(K);
    if (!mp.count(K)) mp[K] = ++tott, pos[tott] = K;
    v[mp[K]].push_back((que){i, n});
  }
  for (long long i = 1; i <= tott; i++) {
    long long x = pos[i];
    long long cnt = 0;
    for (long long j = 1; 1ll * prime[j] * prime[j] <= x && j <= pcnt; j++)
      if (x % prime[j] == 0) {
        pri[++cnt] = prime[j];
        while (x % prime[j] == 0) x /= prime[j];
      }
    if (x != 1) pri[++cnt] = x;
    if (!cnt)
      for (long long j = 0; j < v[i].size(); j++) ans[v[i][j].pos] = 0;
    else if (cnt == 1) {
      for (long long j = 0; j < v[i].size(); j++)
        ans[v[i][j].pos] = (v[i][j].w % pri[1] == 0);
    } else if (cnt == 2) {
      long long inv = power(pri[1], pri[2] - 2, pri[2]);
      for (long long j = 0; j < v[i].size(); j++)
        ans[v[i][j].pos] =
            (1ll * pri[1] * (1ll * inv * (v[i][j].w % pri[2]) % pri[2]) <=
             v[i][j].w);
    } else {
      tot = 0;
      memset(last, 0, sizeof(last));
      for (long long j = 0; j < pri[1]; j++) {
        for (long long k = 1; k <= cnt; k++)
          add(j, (j + pri[k]) % pri[1], pri[k]);
      }
      dij(0);
      for (long long j = 0; j < v[i].size(); j++)
        ans[v[i][j].pos] = (dist[v[i][j].w % pri[1]] <= v[i][j].w);
    }
  }
  for (long long i = 1; i <= T; i++) puts(ans[i] ? "YES" : "NO");
}
