#include <bits/stdc++.h>
using std ::pair;
using std ::priority_queue;
using std ::sort;
template <typename T>
T max(T x, T y) {
  return (x > y) ? x : y;
}
template <typename T>
T min(T x, T y) {
  return (x < y) ? x : y;
}
template <typename T>
bool chkmax(T &x, T y) {
  return (x >= y) ? 0 : (x = y, 1);
}
template <typename T>
bool chkmin(T &x, T y) {
  return (x <= y) ? 0 : (x = y, 1);
}
template <typename T>
T read(T &in) {
  in = 0;
  char ch;
  T f = 1;
  while (!isdigit(ch = getchar()))
    if (ch == '-') f = -1;
  while (isdigit(ch)) in = in * 10 + ch - '0', ch = getchar();
  return in *= f;
}
static const int MAX1 = 10000 + 11;
static const int MAX2 = 32000000 + 11;
static const int MAX3 = 100000 + 11;
struct data {
  long long n, k;
  int i;
};
bool operator<(data a, data b) { return a.k < b.k; }
int T;
data q[MAX1];
bool out[MAX1];
bool vis[MAX2];
int prime[1973816];
void Init(int n = 32000000) {
  for (int i = (2), ir = (n); i <= (ir); ++i) {
    if (!vis[i]) prime[++prime[0]] = i;
    for (int j = (1), jr = (prime[0]); j <= (jr); ++j) {
      if (i * prime[j] > n) break;
      vis[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
}
long long Exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) return x = 1, y = 0, a;
  long long g = Exgcd(b, a % b, x, y), tx = x;
  x = y, y = tx - a / b * y;
  return g;
}
void work(long long k, int &id) {
  static long long p[60];
  int cnt = 0;
  long long temp_k = k;
  for (int *i = prime + 1; 1ll * *i * *i <= k; ++i)
    if (k % *i == 0) {
      while (k % *i == 0) k /= *i;
      p[++cnt] = *i;
    }
  if (k != 1) p[++cnt] = k;
  k = temp_k;
  if (cnt == 0)
    while (id <= T && q[id].k == k) out[q[id].i] = false, ++id;
  else if (cnt == 1)
    while (id <= T && q[id].k == k) out[q[id].i] = (q[id].n % k == 0), ++id;
  else if (cnt == 2) {
    long long x, y;
    long long g = Exgcd(p[1], p[2], x, y);
    y = (y % p[1] + p[1]) % p[1];
    while (id <= T && q[id].k == k)
      out[q[id].i] = (q[id].n % p[1] * y % p[1] * p[2] <= q[id].n), ++id;
  } else {
    static long long d[MAX3];
    static bool vis[MAX3];
    memset(d, 0x3f, sizeof(long long) * (p[1] + 1));
    memset(vis, 0, sizeof(bool) * (p[1] + 1));
    priority_queue<pair<long long, int> > Q;
    Q.push(pair<long long, int>(d[0] = 0, 0));
    while (!Q.empty()) {
      int x = Q.top().second;
      Q.pop();
      if (vis[x]) continue;
      vis[x] = 1;
      for (int i = (2), ir = (cnt); i <= (ir); ++i) {
        int y = (x + p[i]) % p[1];
        if (chkmin(d[y], d[x] + p[i])) Q.push(pair<long long, int>(-d[y], y));
      }
    }
    while (id <= T && q[id].k == k)
      out[q[id].i] = (d[q[id].n % p[1]] <= q[id].n), ++id;
  }
}
int main() {
  Init();
  read(T);
  for (int i = (1), ir = (T); i <= (ir); ++i)
    read(q[i].n), read(q[i].k), q[i].i = i;
  sort(1 + q, 1 + T + q);
  int i = 1;
  while (i <= T) work(q[i].k, i);
  for (int i = (1), ir = (T); i <= (ir); ++i) puts(out[i] ? "YES" : "NO");
  return 0;
}
