#include <bits/stdc++.h>
using namespace std;
inline void clampmod(long long &a, long long mod) {
  a %= mod;
  if (a < 0) a += mod;
}
long long mulmod(long long a, long long b, long long mod) {
  clampmod(a, mod);
  clampmod(b, mod);
  long long res = 0;
  while (b != 0) {
    if (b & 1LL) {
      res = (res + a) % mod;
    }
    a = (a * 2) % mod;
    b /= 2;
  }
  return res;
}
long long powmod(long long x, long long e, long long mod) {
  if (e == 0) {
    return 1LL;
  }
  long long h = powmod(x, e / 2, mod);
  if (e % 2 == 0) {
    return mulmod(h, h, mod);
  } else {
    return mulmod(x, mulmod(h, h, mod), mod);
  }
}
struct query_t {
  long long n, k;
  int id;
  bool operator<(const query_t &x) const {
    return k != x.k ? k < x.k : id < x.id;
  }
} query[10004];
bool ans[10004];
vector<long long> allprimes;
const long long HIGH = 31622800;
bitset<HIGH> isprime;
void sieve() {
  isprime.set();
  for (long long i = 2; i * i < HIGH; ++i) {
    if (isprime[i]) {
      for (long long j = i * i; j < HIGH; j += i) {
        isprime[j] = 0;
      }
    }
  }
  for (long long i = 2; i < HIGH; ++i) {
    if (isprime[i]) {
      allprimes.push_back(i);
    }
  }
}
void factorize(long long k, vector<long long> &primes) {
  for (long long p : allprimes) {
    if (p * p > k) {
      break;
    }
    if (k % p == 0) {
      while (k % p == 0) {
        k /= p;
      }
      primes.push_back(p);
    }
  }
  if (k != 1) {
    primes.push_back(k);
  }
}
int gsz;
vector<pair<long long, int>> g[100005];
long long dist[100005];
void build_graph(const vector<long long> &primes) {
  assert(((int)(primes).size()) >= 3);
  gsz = primes[0];
  for (int i = 0; i < gsz; ++i) {
    g[i].clear();
  }
  for (int i = 0; i < gsz; ++i) {
    for (int j = 1; j < ((int)(primes).size()); ++j) {
      int k = (int)((1LL * i + primes[j]) % (1LL * gsz));
      g[i].push_back({primes[j], k});
      g[k].push_back({primes[j], k});
    }
  }
}
void dijkstra(int start) {
  priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                 greater<pair<long long, int>>>
      pq;
  pq.push({0, start});
  fill(dist, dist + gsz, numeric_limits<long long>::max());
  dist[start] = 0;
  while (!pq.empty()) {
    int u;
    long long d;
    tie(d, u) = pq.top();
    pq.pop();
    if (d != dist[u]) continue;
    for (auto e : g[u]) {
      if (dist[e.second] == numeric_limits<long long>::max() ||
          dist[e.second] > e.first + d) {
        dist[e.second] = e.first + d;
        pq.push({dist[e.second], e.second});
      }
    }
  }
}
void mmain() {
  sieve();
  int t;
  scanf("%d", &t);
  for (int i = 0; i < t; ++i) {
    scanf("%lld %lld", &query[i].n, &query[i].k);
    query[i].id = i;
  }
  sort(query, query + t);
  int lo = 0, hi = 0;
  while (lo < t) {
    while (hi + 1 < t && query[hi + 1].k == query[lo].k) {
      ++hi;
    }
    long long k = query[lo].k;
    ;
    if (k == 1) {
      lo = hi + 1;
      continue;
    }
    vector<long long> primes;
    factorize(k, primes);
    if (((int)(primes).size()) == 1) {
      ;
      for (int i = lo; i <= hi; ++i) {
        if (query[i].n % primes[0] == 0) {
          ans[query[i].id] = 1;
        }
      }
    } else if (((int)(primes).size()) == 2) {
      long long p1 = primes[0], p2 = primes[1];
      ;
      for (int i = lo; i <= hi; ++i) {
        if (query[i].n > p1 * p2 - p1 - p2) {
          ans[query[i].id] = 1;
        } else {
          long long inv2 = powmod(p2, p1 - 2, p1);
          assert(mulmod(inv2, p2, p1) == 1);
          long long y0 = mulmod(query[i].n, inv2, p1);
          assert(query[i].n % p1 == mulmod(p2, y0, p1));
          long long x0 = (query[i].n - p2 * y0) / p1;
          assert(x0 * p1 + y0 * p2 == query[i].n);
          ;
          if (x0 < 0) {
            long long toadd = (-x0) % p2 == 0 ? (-x0) / p2 : (-x0) / p2 + 1;
            x0 += toadd * p2;
            y0 -= toadd * p1;
          }
          if (y0 < 0) {
            long long toadd = (-y0) % p1 == 0 ? (-y0) / p1 : (-y0) / p1 + 1;
            y0 += toadd * p1;
            x0 -= toadd * p2;
          }
          if (x0 >= 0 && y0 >= 0) {
            ans[query[i].id] = 1;
          }
        }
      }
    } else {
      ;
      build_graph(primes);
      dijkstra(0);
      for (int i = lo; i <= hi; ++i) {
        if (query[i].n >= dist[query[i].n % primes[0]]) {
          ans[query[i].id] = 1;
        }
      }
    }
    lo = hi + 1;
  }
  for (int i = 0; i < t; ++i) {
    if (ans[i]) {
      printf("YES\n");
    } else {
      printf("NO\n");
    }
  }
}
int main() { mmain(); }
