#include <bits/stdc++.h>
using namespace std;
const long long INF = (long long)1e9 * (long long)1e9;
const int T = 1e4 + 10, SQ = 32 * 1e6, N = 1e5 + 10;
long long n[T], k[T], dp[N];
int ans[T], q;
vector<int> cheat;
bitset<SQ> not_prime;
long long power(long long a, long long b, long long mod) {
  if (b == 0) return 1;
  long long res = power(a, b / 2, mod);
  res *= res, res %= mod;
  if (b & 1) res *= a, res %= mod;
  return res;
}
inline void calculate(vector<long long> &v) {
  long long sz = v.size(), p = v[0];
  for (int i = 1; i < p; i++) dp[i] = INF;
  set<pair<long long, int> > st;
  st.insert({0, 0});
  while (st.size()) {
    auto r = st.begin()->second;
    st.erase(st.begin());
    for (int i = 1; i < sz; i++) {
      int rp = ((long long)r + v[i]) % p;
      if (dp[rp] > dp[r] + v[i]) {
        st.erase({dp[rp], rp});
        dp[rp] = dp[r] + v[i];
        st.insert({dp[rp], rp});
      }
    }
  }
  return;
}
inline void solve(int p) {
  long long y = k[p];
  vector<long long> primes;
  for (auto i : cheat) {
    if (y % i == 0) {
      primes.push_back(i);
      while (y % i == 0) y /= i;
    }
  }
  if (y > 1) primes.push_back(y);
  int sz = primes.size();
  if (sz >= 3) {
    calculate(primes);
    long long p0 = primes[0];
    for (int i = 0; i < q; i++) {
      if (k[i] == k[p]) {
        long long x = n[i];
        if (dp[x % p0] <= x)
          ans[i] = 1;
        else
          ans[i] = 0;
      }
    }
    return;
  }
  if (sz == 2) {
    for (int i = 0; i < q; i++) {
      if (k[i] == k[p]) {
        long long x = n[i];
        long long p0 = primes[0], q0 = primes[1];
        long long inv = power(q0, p0 - 2, p0);
        inv *= (x % p0);
        inv %= p0;
        if (q0 * inv <= n[i])
          ans[i] = 1;
        else
          ans[i] = 0;
      }
    }
    return;
  }
  if (sz == 1) {
    for (int i = 0; i < q; i++) {
      if (k[i] == k[p]) {
        long long x = n[i];
        if (x % primes[0] == 0)
          ans[i] = 1;
        else
          ans[i] = 0;
      }
    }
    return;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> q;
  for (int i = 0; i < q; i++) cin >> n[i] >> k[i];
  memset(ans, -1, sizeof ans);
  not_prime[0] = 1;
  for (long long i = 2; i < SQ; i++)
    if (!not_prime[i]) {
      cheat.push_back(i);
      for (long long j = i * i; j < SQ; j += i) not_prime[j] = true;
    }
  for (int i = 0; i < q; i++)
    if (ans[i] == -1) solve(i);
  for (int i = 0; i < q; i++)
    if (ans[i])
      cout << "YES\n";
    else
      cout << "NO\n";
}
