#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
using namespace std;
const long long maxn = 1e5 + 123, inf = 1e9, N = 3e7 + 5e6, INF = 1e18,
                mod = 1e9 + 7;
vector<pair<long long, long long> > v, g[maxn];
vector<long long> prime;
bool used[N + 13];
long long t, dis[maxn], n[maxn], k[maxn];
map<pair<long long, long long>, bool> ans;
long long binpow(long long x, long long n, long long mod) {
  long long res = 1;
  while (n) {
    if (n & 1) res = (res * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return res;
}
int main() {
  for (int i = 2; i <= N; i++) {
    if (!used[i]) {
      prime.push_back(i);
      ;
      for (long long j = 1ll * i * i; j < N; j += i) used[j] = 1;
    }
  }
  scanf("%lld", &t);
  for (int i = 0; i < t; i++) {
    scanf("%lld%lld", &n[i], &k[i]);
    v.push_back(make_pair(k[i], n[i]));
  }
  sort(v.begin(), v.end());
  for (int i = 0; i < t;) {
    long long k = v[i].first, x = v[i].first;
    vector<long long> vn, p;
    while (i <= t && k == v[i].first) vn.push_back(v[i++].second);
    for (int i = 0; i < prime.size(); i++) {
      if (x % prime[i] == 0) {
        p.push_back(prime[i]);
        while (x % prime[i] == 0) x /= prime[i];
      }
    }
    if (x > 1) p.push_back(x);
    if (p.size() == 1) {
      for (int i = 0; i < vn.size(); i++)
        ans[make_pair(vn[i], k)] = (vn[i] % p[0] == 0);
    }
    if (p.size() == 2) {
      long long x = p[0], y = p[1];
      for (int i = 0; i < vn.size(); i++) {
        long long n = vn[i], a, b;
        b = n % x * binpow(y, x - 2, x) % x;
        ans[make_pair(n, k)] = (n >= b * y);
      }
    }
    if (p.size() >= 3) {
      for (int i = 0; i < p[0]; i++) {
        g[i].clear();
        for (int j = 0; j < p.size(); j++)
          g[i].push_back(make_pair((i + p[j]) % p[0], p[j]));
        dis[i] = INF;
      }
      set<pair<long long, long long> > st;
      dis[0] = 0;
      st.insert(make_pair(0, 0));
      while (!st.empty()) {
        long long v = (*st.begin()).second;
        st.erase(st.begin());
        for (int i = 0; i < g[v].size(); i++) {
          long long to = g[v][i].first, w = g[v][i].second;
          if (dis[to] > dis[v] + w) {
            st.erase(make_pair(dis[to], to));
            dis[to] = dis[v] + w;
            st.insert(make_pair(dis[to], to));
          }
        }
      }
      for (int i = 0; i < vn.size(); i++)
        ans[make_pair(vn[i], k)] = (vn[i] >= dis[vn[i] % p[0]]);
    }
  }
  for (int i = 0; i < t; i++)
    if (ans[make_pair(n[i], k[i])])
      puts("YES");
    else
      puts("NO");
}
