#include <bits/stdc++.h>
using namespace std;
const long long T = 1e4, SQ = 32e6, inf = 1e18 + 10;
bool notprime[SQ], ans[T];
vector<int> primes;
map<long long, vector<pair<long long, int> > > mapk;
long long euclid(long long x, long long y, long long &z1, long long &z2) {
  if (y == 0) {
    z1 = 1;
    z2 = 0;
    return x;
  }
  long long g = euclid(y, x % y, z2, z1);
  z2 -= z1 * (x / y);
  return g;
}
vector<long long> tajzieh(long long k) {
  vector<long long> tmp;
  for (int i = 0; i < primes.size(); i++) {
    if (k % primes[i] == 0) {
      tmp.push_back(primes[i]);
      while (k % primes[i] == 0) k /= primes[i];
    }
  }
  if (k > 1) tmp.push_back(k);
  return tmp;
}
void answer(long long k, vector<pair<long long, int> > q) {
  vector<long long> kprimes = tajzieh(k);
  if (kprimes.size() == 0)
    return;
  else if (kprimes.size() == 1) {
    for (auto query : q) {
      if (query.first % kprimes[0] == 0) ans[query.second] = 1;
    }
    return;
  } else if (kprimes.size() == 2) {
    long long z1 = 0, z2 = 0;
    long long x = kprimes[0], y = kprimes[1];
    euclid(x, y, z1, z2);
    z2 %= x;
    if (z2 < 0) z2 += x;
    for (auto query : q) {
      long long tmp = (z2 * (query.first % x) % x) * y;
      if (tmp <= query.first) ans[query.second] = 1;
    }
    return;
  }
  int m = kprimes[0];
  long long dis[m];
  for (int i = 0; i < m; i++) dis[i] = inf;
  dis[0] = 0;
  set<pair<long long, long long> > dij;
  dij.insert({0, 0});
  while (!dij.empty()) {
    int x = dij.begin()->second;
    dij.erase(dij.begin());
    for (int i = 1; i < kprimes.size(); i++) {
      long long y = (x + kprimes[i]) % m;
      if (dis[x] + kprimes[i] < dis[y]) {
        dij.erase({dis[y], y});
        dis[y] = dis[x] + kprimes[i];
        dij.insert({dis[y], y});
      }
    }
  }
  for (auto query : q) {
    if (dis[query.first % m] <= query.first) ans[query.second] = 1;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  for (int i = 2; i < SQ; i++) {
    if (notprime[i] == 0) {
      primes.push_back(i);
      for (int j = i * 2; j < SQ; j += i) notprime[j] = 1;
    }
  }
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    long long n, k;
    cin >> n >> k;
    mapk[k].push_back({n, i});
  }
  for (auto i : mapk) answer(i.first, i.second);
  for (int i = 0; i < t; i++) {
    if (ans[i] == 1)
      cout << "YES\n";
    else
      cout << "NO\n";
  }
}
