#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool chkmin(T& x, T y) {
  return x > y ? x = y, true : false;
}
template <class T>
inline bool chkmax(T& x, T y) {
  return x < y ? x = y, true : false;
}
const long long MAXN = 1e18;
const long long MAXK = 1e15;
const long long INF = 4e18;
const int MAXV = 3.2e7 + 5;
const int MAXP = 2e6 + 10;
const int MAXF = 1e5 + 10;
const int MAXQ = 50;
const int MAXLOG = 64;
long long n, k, tot, q;
int f[MAXV], prime[MAXP], cnt[MAXQ + 1];
long long p[MAXQ + 1][MAXLOG], dist[MAXQ + 1][MAXF];
long long mem[MAXQ];
bool vis[MAXP];
template <typename T>
inline void read(T& x) {
  long long f = 1;
  x = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -f;
  for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
  x *= f;
}
inline long long ppow(long long a, long long b, long long MO) {
  long long ret = 1;
  for (; b; b >>= 1) {
    if (b & 1) ret = ret * a % MO;
    a = a * a % MO;
  }
  return ret;
}
int main() {
  int T;
  read(T);
  for (int i = (2); i <= (MAXV - 1); ++i) {
    if (!f[i]) prime[++tot] = f[i] = i;
    for (int j = (1); j <= (tot); ++j) {
      int tmp = i * prime[j];
      if (tmp >= MAXV) break;
      f[tmp] = prime[j];
      if (f[i] == prime[j]) break;
    }
  }
  while (T--) {
    read(n);
    read(k);
    if (k == 1) {
      printf("NO\n");
      continue;
    }
    int pos = 0;
    for (int i = (1); i <= (q); ++i)
      if (mem[i] == k) pos = i;
    if (!pos) {
      pos = ++q;
      mem[pos] = k;
      cnt[pos] = 0;
      for (int i = 1; 1ll * prime[i] * prime[i] <= k; i++) {
        if (k % prime[i] == 0) {
          p[pos][++cnt[pos]] = prime[i];
          while (k % prime[i] == 0) k /= prime[i];
        }
      }
      if (k != 1) p[pos][++cnt[pos]] = k;
      if (cnt[pos] >= 3) {
        for (int i = 0; i < p[pos][1]; i++) {
          dist[pos][i] = INF;
          vis[i] = false;
        }
        dist[pos][0] = 0;
        static priority_queue<pair<long long, int> > q;
        q.push(make_pair(0, 0));
        while (!q.empty()) {
          int u = q.top().second;
          q.pop();
          if (vis[u]) continue;
          vis[u] = true;
          for (int i = (2); i <= (cnt[pos]); ++i) {
            int to = (u + p[pos][i]) % p[pos][1];
            int w = p[pos][i];
            if (dist[pos][u] + w < dist[pos][to]) {
              dist[pos][to] = dist[pos][u] + w;
              q.push(make_pair(-dist[pos][to], to));
            }
          }
        }
      }
    }
    if (cnt[pos] == 1) {
      if (n % p[pos][1] == 0) {
        puts("YES");
        continue;
      } else {
        puts("NO");
        continue;
      }
    }
    if (cnt[pos] == 2) {
      long long b =
          n % p[pos][1] * ppow(p[pos][2], p[pos][1] - 2, p[pos][1]) % p[pos][1];
      if (b * p[pos][2] <= n)
        puts("YES");
      else
        puts("NO");
      continue;
    }
    int val = n % p[pos][1];
    if (n >= dist[pos][val])
      puts("YES");
    else
      puts("NO");
  }
  return 0;
}
