#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
const int M = 4e7;
int pr[M / 10];
int prSz = 0;
bool np[M];
long long mod;
long long mul(long long a, long long b) {
  a %= mod;
  b %= mod;
  long long q = (long long)(1.0 * a * b / mod);
  long long r = a * b - q * mod;
  r %= mod;
  if (r < 0) r += mod;
  return r;
}
long long g(long long x) {
  long long ans = mul(x, x) + 1;
  if (ans >= mod) ans -= mod;
  return ans;
}
vector<long long> factorization(long long x) {
  vector<long long> res;
  for (int i = 0; i < prSz; i++) {
    if (x % pr[i]) continue;
    res.push_back(pr[i]);
    while (x % pr[i] == 0) x /= pr[i];
  }
  if (x > 1) res.push_back(x);
  return res;
}
long long euclid(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = euclid(b, a % b, y, x);
  y -= x * (a / b);
  return d;
}
bool ans[N];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for (int i = 2; i < M; ++i)
    if (!np[i]) {
      pr[prSz++] = i;
      for (long long j = 1ll * i * i; j < M; j += i) np[j] = 1;
    }
  map<long long, vector<pair<long long, int> > > mp;
  int itest;
  cin >> itest;
  for (int i = 0; i < itest; ++i) {
    long long n;
    cin >> n;
    long long k;
    cin >> k;
    mp[k].emplace_back(n, i);
  }
  for (auto it : mp) {
    vector<long long> vec = factorization(it.first);
    if (vec.size() == 0) continue;
    if (vec.size() == 1) {
      for (pair<long long, int> T : it.second)
        ans[T.second] = (T.first % vec[0] == 0);
      continue;
    }
    if (vec.size() == 2) {
      long long a, b;
      assert(euclid(vec[0], vec[1], a, b) == 1);
      b %= vec[0];
      b += vec[0];
      b %= vec[0];
      for (pair<long long, int> T : it.second)
        ans[T.second] = (b * (T.first % vec[0]) % vec[0]) * vec[1] <= T.first;
      continue;
    }
    vector<long long> d(vec[0], 1e18);
    priority_queue<pair<long long, int>, vector<pair<long long, int> >,
                   greater<pair<long long, int> > >
        pq;
    pq.push(pair<long long, int>(0, 0));
    d[0] = 0;
    while (pq.size()) {
      int u = pq.top().second;
      long long du = pq.top().first;
      pq.pop();
      if (du != d[u]) continue;
      for (long long x : vec) {
        long long v = (x + u) % vec[0];
        if (d[v] > du + x) {
          d[v] = du + x;
          pq.push(pair<long long, int>(d[v], v));
        }
      }
    }
    for (pair<long long, int> T : it.second)
      ans[T.second] = (T.first >= d[T.first % vec[0]]);
  }
  for (int i = 0; i < itest; ++i) {
    if (ans[i])
      cout << "YES\n";
    else
      cout << "NO\n";
  }
}
