#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void in(T &x) {
  x = 0;
  char c = getchar();
  bool f = 0;
  while (!isdigit(c)) f |= (c == '-'), c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ '0'), c = getchar();
  f ? x = -x : 0;
}
template <class T>
inline void out(T x, const char c = '\n') {
  static short st[30];
  short m = 0;
  if (x < 0) putchar('-'), x = -x;
  do st[++m] = x % 10, x /= 10;
  while (x);
  while (m) putchar(st[m--] | '0');
  putchar(c);
}
template <class T>
inline void err(const T &x, const char c = '\n') {
  cerr << x << c;
}
template <class T, class... Args>
inline void in(T &x, Args &...args) {
  in(x);
  in(args...);
}
template <class T, class... Args>
inline void out(const T &x, const Args &...args) {
  out(x, ' ');
  out(args...);
}
template <class T, class... Args>
inline void err(const T &x, const Args &...args) {
  err(x, ' ');
  err(args...);
}
template <class T>
inline void prt(T a[], int n) {
  for (register int i = 0; i < n; ++i) out(a[i], i == n - 1 ? '\n' : ' ');
}
template <class T>
inline void clr(T a[], int n) {
  memset(a, 0, sizeof(T) * n);
}
template <class T>
inline void clr(T *a, T *b) {
  memset(a, 0, sizeof(T) * (b - a));
}
template <class T>
inline bool ckmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
template <class T>
inline bool ckmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
namespace i207M {
bitset<31622777> notp;
int pri[2000000], cntp;
void sieve(int n) {
  notp[1] = 1;
  for (register int i = 2; i <= n; ++i) {
    if (!notp[i]) pri[++cntp] = i;
    for (register int j = 1, t; j <= cntp && (t = pri[j] * i) <= n; ++j) {
      notp[t] = 1;
      if (i % pri[j] == 0) break;
    }
  }
}
bool ans[10005];
vector<long long> d;
void divi(long long x) {
  d.clear();
  for (register int i = 1; i <= cntp && (long long)pri[i] * pri[i] <= x; ++i)
    if (x % pri[i] == 0) {
      d.push_back(pri[i]);
      while (x % pri[i] == 0) x /= pri[i];
    }
  if (x > 1) d.push_back(x);
}
inline long long qmul(const long long &a, const long long &b,
                      const long long &md) {
  long long c = a * b - (long long)((long double)a * b / md + 0.5) * md;
  return c < 0 ? c + md : c;
}
inline long long qpow(long long a, long long b, const long long &md) {
  long long r = 1;
  for (; b; b >>= 1, a = qmul(a, a, md))
    if (b & 1) r = qmul(r, a, md);
  return r;
}
void solve(long long K, const vector<pair<long long, int> > &Q) {
  if (K == 1) return;
  divi(K);
  if (((int)d.size()) == 1) {
    long long t = d[0];
    for (const auto &it : Q) ans[it.second] = (it.first % t == 0);
    return;
  }
  if (((int)d.size()) == 2) {
    long long a = d[0], b = d[1];
    for (const auto &it : Q) {
      long long n = it.first;
      if (n % a == 0 || n % b == 0) {
        ans[it.second] = 1;
        continue;
      }
      long long y = qmul(n % a, qpow(b, a - 2, a), a);
      ans[it.second] = (b * y <= n && (n - b * y) % a == 0);
    }
    return;
  }
  static long long dis[100005];
  static bool ins[100005];
  static queue<int> q;
  memset(dis, 0x3f, sizeof(dis));
  q.push(0), dis[0] = 0;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    ins[x] = 0;
    for (register int i = 1; i < ((int)d.size()); ++i) {
      int v = (x + d[i]) % d[0];
      if (ckmin(dis[v], dis[x] + d[i]) && !ins[v]) q.push(v), ins[v] = 1;
    }
  }
  for (const auto &it : Q) ans[it.second] = (dis[it.first % d[0]] <= it.first);
}
map<long long, vector<pair<long long, int> > > rem;
signed main() {
  int T;
  long long a, b;
  in(T);
  sieve(31622776);
  for (register int i = 1; i <= T; ++i) {
    in(a, b);
    rem[b].push_back(make_pair(a, i));
  }
  for (const auto &it : rem) solve(it.first, it.second);
  for (register int i = 1; i <= T; ++i) puts(ans[i] ? "YES" : "NO");
  return 0;
}
}  // namespace i207M
signed main() {
  i207M::main();
  return 0;
}
