#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
using std::abs;
using std::cerr;
using std::cin;
using std::cout;
using std::map;
using std::max;
using std::min;
using std::pair;
using std::set;
using std::string;
using std::swap;
using std::vector;
using ll = long long;
using uint = unsigned int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ull = unsigned long long;
using ld = long double;
template <typename T>
void _dbg(const char *_s, T _h) {
  cerr << _s << " = " << _h << "\n";
}
template <typename T, typename... Ts>
void _dbg(const char *_s, T _h, Ts... _t) {
  int _b = 0;
  while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',') cerr << *_s++;
  cerr << " = " << _h << ",";
  _dbg(_s + 1, _t...);
}
struct init {
  init() {
    cin.tie(0);
    std::iostream::sync_with_stdio(0);
    cout << std::fixed << std::setprecision(10);
    cerr << std::fixed << std::setprecision(5);
  }
  ~init() {}
} init;
const int MAXN = 35e6;
const ll INF = 2e18;
int lp[MAXN];
int pr[2146775];
int cpr = 0;
void calc_primes(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!lp[i]) {
      lp[i] = i;
      pr[cpr++] = i;
    }
    for (int j = 0; j < cpr && pr[j] <= lp[i] && i * pr[j] <= n; ++j)
      lp[i * pr[j]] = pr[j];
  }
}
vector<ll> fct(ll k) {
  ll x = k;
  vector<ll> res;
  for (int j = 0; j < cpr && pr[j] * 1LL * pr[j] <= k; ++j) {
    if (x % pr[j] == 0) {
      res.emplace_back(pr[j]);
      while (x % pr[j] == 0) x /= pr[j];
    }
  }
  if (x ^ 1LL) res.emplace_back(x);
  return res;
}
ll mulmod(ll a, ll b, ll m) {
  int sign = 1;
  if (a < 0) {
    a = -a;
    sign = -sign;
  }
  if (b < 0) {
    b = -b;
    sign = -sign;
  }
  a %= m;
  b %= m;
  ull q = (ld)a * (ld)b / (ld)m;
  ull r = a * b - q * m;
  return (sign * (ll)(((r + 5 * m) % m + m) % m)) % m;
}
template <typename T>
T extgcd(T a, T b, T &x, T &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  T p = b / a;
  T g = extgcd(b - p * a, a, y, x);
  x -= p * y;
  return g;
}
template <typename T>
bool diophant(T a, T b, T c, T &x, T &y, T &g) {
  if (a == 0 && b == 0) {
    if (c == 0) {
      x = y = g = 0;
      return true;
    }
    return false;
  }
  if (a == 0) {
    if (c % b == 0) {
      x = 0;
      y = c / b;
      g = abs(b);
      return true;
    }
    return false;
  }
  if (b == 0) {
    if (c % a == 0) {
      x = c / a;
      y = 0;
      g = abs(a);
      return true;
    }
    return false;
  }
  g = extgcd(a, b, x, y);
  if (c % g != 0) {
    return false;
  }
  T dx = c / a;
  c -= dx * a;
  T dy = c / b;
  c -= dy * b;
  x = dx + mulmod(x, c / g, b);
  y = dy + mulmod(y, c / g, a);
  g = abs(g);
  return true;
}
int32_t main() {
  calc_primes(MAXN - 1);
  ;
  int t;
  cin >> t;
  map<ll, vector<ll>> dv, dts;
  while (t--) {
    ll n, k;
    cin >> n >> k;
    if (dv.find(k) == dv.end()) dv[k] = fct(k);
    vector<ll> ps = dv[k];
    for (int i : ps)
      ;
    if (ps.empty())
      cout << "NO\n";
    else if (ps.size() == 1) {
      if (n % k == 0)
        cout << "YES\n";
      else
        cout << "NO\n";
    } else if (ps.size() == 2) {
      ll x, y, g;
      if (!diophant(ps[0], ps[1], n, x, y, g))
        cout << "NO\n";
      else {
        ;
        if (x < 0) {
          int bg = ps[1] / g;
          int need = (-x + bg - 1) / bg;
          x += bg * need;
          y -= ps[0] / g * need;
        }
        if (y < 0) {
          int ag = ps[0] / g;
          int need = (-y + ag - 1) / ag;
          y += ag / need;
          x -= ps[1] / g * need;
        }
        if (x >= 0 && y >= 0)
          cout << "YES\n";
        else
          cout << "NO\n";
      }
    } else {
      ;
      if (dts.find(k) == dts.end()) {
        vector<ll> d(ps[0], INF);
        d[0] = 0;
        set<pll> s;
        s.insert({0, 0});
        while (!s.empty()) {
          pll v = *s.begin();
          s.erase(s.begin());
          for (int i = 1; i < ps.size(); ++i) {
            ll to = (v.second + ps[i]) % ps[0];
            ll len = ps[i];
            if (d[to] > v.first + len) {
              s.erase({d[to], to});
              s.insert({d[to] = v.first + len, to});
            }
          }
        }
        dts[k] = d;
      }
      if (n >= dts[k][n % ps[0]])
        cout << "YES\n";
      else
        cout << "NO\n";
    }
  }
  return 0;
}
