#include <bits/stdc++.h>
using namespace std;
const int MXP = 4e7;
bitset<MXP> prime;
vector<long long> primes;
void sieve() {
  for (int p = 2; p < MXP; p++) {
    if (prime[p]) continue;
    primes.push_back(p);
    for (int q = p; q < MXP; q += p) prime.set(q);
  }
}
map<long long, vector<pair<long long, int>>> qry;
bool ans[10005];
vector<pair<long long, long long>> adj[100005];
long long dis[100005];
long long euclid(long long a, long long b, long long &x, long long &y) {
  if (b) {
    long long d = euclid(b, a % b, y, x);
    return y -= a / b * x, d;
  }
  return x = 1, y = 0, a;
}
void solve(long long k, vector<pair<long long, int>> &qs) {
  if (k == 1) {
    for (auto q : qs) ans[q.second] = false;
    return;
  }
  vector<long long> pf;
  for (auto p : primes) {
    if (p * p > k) break;
    if (k % p) continue;
    pf.push_back(p);
    while (k % p == 0) k /= p;
  }
  if (k > 1) pf.push_back(k);
  sort(pf.begin(), pf.end());
  if (pf.size() == 1) {
    for (auto q : qs) ans[q.second] = (q.first % pf[0] == 0);
    return;
  }
  if (pf.size() == 2) {
    long long x, y;
    long long p = pf[0], q = pf[1];
    euclid(q, p, x, y);
    x = (x % p + p) % p;
    for (auto qry : qs) {
      long long n = qry.first;
      long long d = n % p;
      long long fi = ((n % p) * x) % p;
      ans[qry.second] = (q * fi <= n);
    }
    return;
  }
  for (int i = 0; i < pf[0]; i++) {
    adj[i].clear();
    for (int j = 1; j < pf.size(); j++) {
      long long p = pf[j];
      adj[i].push_back({(i + p) % pf[0], p});
    }
  }
  fill(dis, dis + pf[0], LLONG_MAX);
  priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,
                 greater<pair<long long, long long>>>
      q;
  dis[0] = 0;
  q.push({0, 0});
  while (!q.empty()) {
    long long d = q.top().first, u = q.top().second;
    q.pop();
    if (d > dis[u]) continue;
    for (auto e : adj[u]) {
      long long v = e.first, w = e.second;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({dis[v], v});
      }
    }
  }
  for (auto q : qs) ans[q.second] = (dis[q.first % pf[0]] <= q.first);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  sieve();
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    long long n, k;
    cin >> n >> k;
    qry[k].push_back({n, i});
  }
  for (auto p : qry) solve(p.first, p.second);
  for (int i = 0; i < t; i++) cout << (ans[i] ? "YES\n" : "NO\n");
}
