#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
const int N = 1e5 + 5;
const long long INF = (long long)2e18;
template <class T>
inline void read(T &x) {
  x = 0;
  int c = getchar(), f = 1;
  for (; !isdigit(c); c = getchar())
    if (c == 45) f = -1;
  for (; isdigit(c); c = getchar()) (x *= 10) += f * (c - '0');
}
vector<int> pl, spf;
int _;
map<long long, vector<pair<long long, int>>> mapchik;
long long dis[N];
bool ans[N];
inline unsigned long long mul_mod(unsigned long long a, unsigned long long b,
                                  unsigned long long mod) {
  assert(0 <= a && a < mod);
  assert(0 <= b && b < mod);
  if (mod < int(1e9)) return a * b % mod;
  unsigned long long k = (unsigned long long)((long double)a * b / mod);
  unsigned long long res = a * b - k * mod;
  if ((unsigned long long)res < 0) res += mod;
  return res;
}
void exgcd(long long a, long long b, long long &g, long long &x, long long &y) {
  if (!b)
    g = a, x = 1, y = 0;
  else {
    exgcd(b, a % b, g, y, x);
    y -= x * (a / b);
  }
}
void fast_sieve(int n) {
  pl.clear();
  spf.assign(n, 0);
  for (int i = 2; i < n; ++i) {
    if (!spf[i]) {
      pl.push_back(i);
      spf[i] = i;
    }
    for (int j = 0; j < ((int)(pl).size()) && i * pl[j] < n; ++j) {
      int p = pl[j];
      spf[i * p] = p;
      if (i % p == 0) break;
    }
  }
}
vector<long long> factorize(long long n) {
  vector<long long> u;
  for (int i = 0, t = sqrt(n + 1); pl[i] <= t; ++i)
    if (n % pl[i] == 0) {
      u.push_back(pl[i]);
      while (n % pl[i] == 0) n /= pl[i];
      t = sqrt(n + 1);
    }
  if (n > 1) u.push_back(n);
  return u;
}
void solve(long long k, vector<pair<long long, int>> queries) {
  vector<long long> p = factorize(k);
  int n = ((int)(p).size());
  if (n == 0) return;
  if (n == 1) {
    for (auto &q : queries) ans[q.second] = q.first % p[0] == 0;
    return;
  }
  if (n == 2) {
    long long a = p[0], b = p[1], g, x, y;
    exgcd(a, b, g, x, y);
    for (auto &q : queries)
      ans[q.second] = (((y % a * (q.first % a) % a + a) % a) * b) <= q.first;
    return;
  }
  for (int i = 0; i < p[0]; ++i) dis[i] = INF;
  dis[0] = 0;
  set<pair<long long, int>> pq;
  for (int i = 0; i < p[0]; ++i) pq.insert(make_pair(dis[i], i));
  while (!pq.empty()) {
    int u = (*pq.begin()).second;
    pq.erase(pq.begin());
    for (int i = 1; i < n; ++i) {
      int v = (u + p[i]) % p[0];
      long long w = dis[u] + p[i];
      if (w >= dis[v]) continue;
      pq.erase(make_pair(dis[v], v));
      dis[v] = w;
      pq.insert(make_pair(dis[v], v));
    }
  }
  for (auto &q : queries) ans[q.second] = dis[q.first % p[0]] <= q.first;
}
int main() {
  fast_sieve((int)35e6 + 5);
  read(_);
  for (int i = 0; i < _; ++i) {
    long long n, k;
    read(n);
    read(k);
    mapchik[k].push_back(make_pair(n, i));
  }
  for (auto &it : mapchik) solve(it.first, it.second);
  for (int i = 0; i < _; ++i)
    if (ans[i])
      puts("YES");
    else
      puts("NO");
}
