#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int maxt = 10010;
const int maxn = 100010;
int T;
long long q_n[maxt], q_k[maxt];
int p_list[10000010], isnp[40000010], tot;
vector<long long> vec;
map<long long, int> k_id;
long long mul(long long a, long long b, long long mod) {
  long long ret = 0;
  for (int i = 0; i < 63; i++) {
    if ((a >> i) & 1) ret = (ret + b) % mod;
    b = b * 2 % mod;
  }
  return ret;
}
long long gcd(long long a, long long b) {
  if (!b) return a;
  return gcd(b, a % b);
}
long long qpow(long long x, long long y, long long mod) {
  long long ret = 1;
  while (y) {
    if (y & 1) ret = 1LL * ret * x % mod;
    x = 1LL * x * x % mod;
    y >>= 1;
  }
  return ret;
}
void _find(long long n, vector<long long> &vec) {
  for (int i = 1; i <= tot; i++) {
    while (n % p_list[i] == 0) {
      vec.push_back(p_list[i]);
      n /= p_list[i];
    }
  }
  if (n > 1) vec.push_back(n);
}
struct ShortestPath {
  long long k, minp;
  int ps;
  stack<long long> st;
  vector<long long> prm;
  long long dis[maxn];
  void init() {
    minp = 2e18;
    if (k > 1) _find(k, prm);
    for (int i = 0; i < prm.size(); i++) minp = min(minp, prm[i]);
    ps = int(prm.size());
    sort(prm.begin(), prm.end());
    prm.erase(unique(prm.begin(), prm.end()), prm.end());
    if (ps >= 3) {
      for (int i = 0; i < minp; i++) {
        dis[i] = 2e18;
      }
      dis[0] = 0;
      priority_queue<pair<long long, int>, vector<pair<long long, int> >,
                     greater<pair<long long, int> > >
          pq;
      pq.push(pair<long long, int>(dis[0], 0));
      while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        for (int i = 0; i < prm.size(); i++) {
          long long p = prm[i];
          int v = (u + p) % minp;
          if (dis[u] + p < dis[v]) {
            dis[v] = dis[u] + p;
            pq.push(pair<long long, int>(dis[v], v));
          }
        }
      }
    }
  }
  int query(long long n) {
    if (ps == 0) {
      return 0;
    } else if (ps == 1) {
      return (n % prm[0] == 0);
    } else if (ps == 2) {
      long long p1 = prm[0], p2 = prm[1];
      if (p1 == p2) return (n % p1 == 0);
      if (p1 == minp) swap(p1, p2);
      long long r = n % p1;
      long long t = qpow(p2, p1 - 2, p1);
      long long k = mul(r, t, p1);
      return k * p2 <= n;
    } else {
      return (dis[n % minp] <= n);
    }
  }
} shortestPath[55];
int main() {
  for (int i = 2; i <= 40000000; i++) {
    if (!isnp[i]) {
      p_list[++tot] = i;
    }
    for (int j = 1; j <= tot && p_list[j] * i <= 40000000; j++) {
      isnp[p_list[j] * i] = 1;
      if (i % p_list[j] == 0) break;
    }
  }
  cin >> T;
  for (int i = 1; i <= T; i++) {
    cin >> q_n[i] >> q_k[i];
    vec.push_back(q_k[i]);
  }
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  for (int i = 0; i < vec.size(); i++) {
    k_id[vec[i]] = i;
    shortestPath[i].k = vec[i];
    shortestPath[i].init();
  }
  for (int i = 1; i <= T; i++) {
    int id = k_id[q_k[i]];
    if (shortestPath[id].query(q_n[i]))
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
  return 0;
}
