#include <bits/stdc++.h>
using namespace std;
const long long maxn = 4e6 + 5;
long long pri[maxn], cnt;
bool p[maxn * 9];
long long P;
void init() {
  for (long long i = 2; i <= P; ++i) {
    if (!p[i]) pri[++cnt] = i;
    for (long long j = 1; j <= cnt && i * pri[j] <= P; ++j) {
      p[i * pri[j]] = 1;
      if (i % pri[j] == 0) break;
    }
  }
}
long long a[50], tot;
long long dis[100005];
vector<pair<int, int>> e[100005];
priority_queue<pair<long long, long long>> Q;
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}
long long gcd(long long a, long long b) {
  if (!b) return a;
  return gcd(b, a % b);
}
map<long long, long long> mp;
long long owo = 0;
vector<pair<long long, long long>> q[100];
long long ans[10010];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  long long T;
  cin >> T;
  P = sqrt(1e15 + 0.5);
  init();
  for (long long _ = 1; _ <= T; ++_) {
    long long n, k;
    cin >> n >> k;
    if (!mp[k]) mp[k] = ++owo;
    q[mp[k]].emplace_back(n, _);
  }
  for (auto xs : mp) {
    long long k, u;
    tie(k, u) = xs;
    tot = 0;
    for (long long i = 1; i <= cnt && 1ll * pri[i] * pri[i] <= k; ++i) {
      if (k % pri[i] == 0) {
        a[++tot] = pri[i];
        while (k % pri[i] == 0) k /= pri[i];
      }
    }
    if (k != 1) a[++tot] = k;
    if (k == 1) {
      for (auto x : q[u]) {
        long long n, id;
        tie(n, id) = x;
        ans[id] = 0;
      }
    } else if (tot == 1) {
      for (auto x : q[u]) {
        long long n, id;
        tie(n, id) = x;
        if (n % a[1])
          ans[id] = 0;
        else
          ans[id] = 1;
      }
    } else if (tot == 2) {
      long long x, y;
      exgcd(a[1], a[2], x, y);
      x = (x % a[2] + a[2]) % a[2];
      for (auto xx : q[u]) {
        long long n, id;
        tie(n, id) = xx;
        long long tx = n % a[2] * x % a[2];
        long long ty = (n - a[1] * tx) / a[2];
        if (ty < 0)
          ans[id] = 0;
        else
          ans[id] = 1;
      }
    } else {
      memset(dis, 0x3f, sizeof dis);
      for (long long i = 0; i < a[1]; ++i) e[i].clear();
      for (long long i = 2; i <= tot; ++i)
        for (long long j = 0; j < a[1]; ++j)
          e[j].emplace_back((j + a[i]) % a[1], a[i]);
      dis[0] = 0;
      Q.emplace(0, 0);
      while (!Q.empty()) {
        long long u;
        long long d;
        tie(d, u) = Q.top();
        Q.pop();
        d = -d;
        if (d != dis[u]) continue;
        for (auto x : e[u]) {
          long long v, w;
          tie(v, w) = x;
          if (dis[v] > dis[u] + w) {
            dis[v] = dis[u] + w;
            Q.emplace(-dis[v], v);
          }
        }
      }
      for (auto x : q[u]) {
        long long n, id;
        tie(n, id) = x;
        if (dis[n % a[1]] <= n)
          ans[id] = 1;
        else
          ans[id] = 0;
      }
    }
  }
  for (long long i = 1; i <= T; ++i) {
    cout << (ans[i] ? "YES" : "NO") << '\n';
  }
  return 0;
}
