#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010, maxm = 33333333, m = 32000000, mod = 998244353;
inline long long read() {
  char ch = getchar();
  long long x = 0, f = 0;
  while (ch < '0' || ch > '9') f |= ch == '-', ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return f ? -x : x;
}
struct ques {
  long long n, k;
  int id;
  bool operator<(const ques &q) const { return k < q.k; }
} q[maxn];
long long tmp[22], f[maxn];
int T, pr[maxm / 10], pl, tl;
bool vis[maxm], ans[maxn];
priority_queue<pair<long long, int>, vector<pair<long long, int> >,
               greater<pair<long long, int> > >
    pq;
void init() {
  for (int i = (2); i <= (m); i++) {
    if (!vis[i]) pr[++pl] = i;
    for (int j = (1); j <= (pl); j++) {
      int k = i * pr[j];
      if (k > m) break;
      vis[k] = true;
    }
  }
}
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) return x = 1, y = 0, a;
  long long d = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
int main() {
  init();
  T = read();
  for (int i = (1); i <= (T); i++) {
    long long n = read(), k = read();
    q[i] = (ques){n, k, i};
  }
  sort(q + 1, q + T + 1);
  for (int i = (1); i <= (T); i++) {
    long long k = q[i].k, ttt = k;
    tl = 0;
    for (int j = (1); j <= (pl); j++)
      if (ttt % pr[j] == 0) {
        tmp[++tl] = pr[j];
        while (ttt % pr[j] == 0) ttt /= pr[j];
      }
    if (ttt > 1) tmp[++tl] = ttt;
    if (tl >= 3) {
      assert(tmp[1] <= 1e5);
      for (int i = (0); i <= (tmp[1] - 1); i++) f[i] = 2e18;
      f[0] = 0;
      while (!pq.empty()) pq.pop();
      pq.push(make_pair(f[0], 0));
      while (!pq.empty()) {
        int u = pq.top().second;
        long long d = pq.top().first;
        pq.pop();
        if (f[u] != d) continue;
        for (int i = (2); i <= (tl); i++) {
          int v = (u + tmp[i]) % tmp[1];
          if (d + tmp[i] < f[v]) pq.push(make_pair(f[v] = d + tmp[i], v));
        }
      }
    }
    for (int j = (i); j <= (T); j++) {
      if (q[j].k != k) {
        i = j - 1;
        break;
      }
      long long n = q[j].n;
      if (!tl)
        ans[q[j].id] = false;
      else if (tl == 1)
        ans[q[j].id] = n % tmp[1] == 0;
      else if (tl == 2) {
        long long a = tmp[1], b = tmp[2], x, y;
        exgcd(a, b, x, y);
        y = (y + a) % a;
        y = n % a * y % a;
        ans[q[j].id] = b * y <= n;
      } else
        ans[q[j].id] = f[n % tmp[1]] <= n;
      if (j == T) i = T;
    }
  }
  for (int i = (1); i <= (T); i++) puts(ans[i] ? "YES" : "NO");
}
