#include <bits/stdc++.h>
using namespace std;
using INT = long long;
INT n, k;
INT multi(INT x, INT y, INT z) {
  return (x * y - (INT)(x / (long double)z * y + 1e-8) * z + z) % z;
}
INT power(INT a, INT y, INT z) {
  if (y == 0) return 1;
  INT b = power(a, y >> 1, z);
  b = multi(b, b, z);
  if (y & 1LL) b = multi(b, a, z);
  return b;
}
bool witness(INT a, INT n) {
  int t = 0;
  INT u = n - 1;
  while (~u & 1LL) {
    u >>= 1;
    t++;
  }
  INT x0 = power(a, u, n), x1;
  for (int i = 0; i < t; i++) {
    x1 = multi(x0, x0, n);
    if (x1 == 1 && x0 != n - 1 && x0 != 1) return true;
    x0 = x1;
  }
  if (x0 != 1) return true;
  return false;
}
INT add(INT x, const INT &y, const INT &z) {
  x += y;
  if (x >= z) return x - z;
  return x;
}
INT gcd(const INT &a, const INT &b) {
  if (!b) return a;
  return gcd(b, a % b);
}
INT pollard(INT n) {
  static mt19937_64 rnd(996);
  static const int maxt = 100;
  while (1) {
    INT x = rnd() % (n - 3) + 2, y = x, c = rnd() % n, tim = 0, prd = 1;
    for (INT i = 1, stp = 2;; ++i) {
      if (i == stp) y = x, stp <<= 1;
      if ((x = add(multi(x, x, n), c, n)) == y) break;
      INT tmp = prd;
      if ((prd = multi(prd, abs(y - x), n)) == 0) return gcd(tmp, n);
      if ((++tim) < maxt) continue;
      if ((prd = gcd(prd, n)) > 1) return prd;
      tim = 0;
    }
    if (tim > 0 && (prd = gcd(prd, n)) > 1) return prd;
  }
}
bool is_prime(INT N) {
  if (N == 1) return false;
  for (int i = 0; i < 70; i++) {
    INT a = (INT)rand() % (N - 1) + 1;
    if (witness(a, N)) return false;
  }
  return true;
}
map<INT, vector<INT> > fac;
vector<INT> calc(INT u) {
  if (fac.count(u)) return fac[u];
  vector<INT> buf;
  INT U = u;
  for (int i = 2; i <= 100000; i++)
    if (u % i == 0) {
      while (u % i == 0) u /= i;
      buf.push_back(i);
    }
  if (u > 1) {
    if (is_prime(u))
      buf.push_back(u);
    else {
      INT v = pollard(u);
      buf.push_back(v);
      if (v != u and u / v != v) {
        buf.push_back(u / v);
      }
      sort(buf.begin(), buf.end());
    }
  }
  fac[U] = buf;
  return buf;
}
int power(int a, int b, int m, int ans = 1) {
  a %= m;
  for (; b; b >>= 1, a = 1ll * a * a % m)
    if (b & 1) {
      ans = 1ll * ans * a % m;
    }
  return ans;
}
int solve2(INT n, INT a, INT b) {
  int y = (INT)n % a * power(b % a, a - 2, a) % a;
  assert((INT)b % a * y % a == n % a);
  return (b * y <= n);
}
int solve3(INT n, INT a, INT b, INT c) {
  INT rev = power(b % a, a - 2, a);
  for (int i = 0; i < a and c * i <= n; i++) {
    if (c * i + rev * ((n - c * i) % a) % a * b <= n) return 1;
  }
  return 0;
}
INT dp[10100];
pair<int, INT> q[1100000];
int solve4(INT n, vector<INT> &buf) {
  if (n >= buf[0] * buf[1]) return 1;
  INT a = buf[0];
  assert(a < 10000);
  for (int i = 0; i < a; i++) {
    dp[i] = n + 1;
  }
  dp[0] = 0;
  int qb = 1, qf = 1;
  q[qb++] = {0, 0};
  int ss = n % a;
  while (qf < qb) {
    auto p = q[qf++];
    if (dp[p.first] != p.second) continue;
    for (auto &u : buf)
      if (u != buf[0]) {
        int s = u % a + p.first;
        if (s >= a) s -= a;
        if (dp[s] > p.second + u) {
          dp[s] = p.second + u;
          if (ss == s) return 1;
          q[qb++] = {s, dp[s]};
        }
      }
  }
  return (dp[ss] <= n);
}
int solve(vector<INT> &buf, INT n) {
  for (auto u : buf)
    if (n % u == 0) return 1;
  if (buf.size() == 1) return 0;
  if (buf.size() == 2) return solve2(n, buf[0], buf[1]);
  if (buf.size() == 3) return solve3(n, buf[0], buf[1], buf[2]);
  return solve4(n, buf);
}
int main() {
  int T;
  cin >> T;
  while (T--) {
    cin >> n >> k;
    if (k == 1) {
      puts("NO");
      continue;
    }
    vector<INT> buf = calc(k);
    if (solve(buf, n))
      puts("YES");
    else
      puts("NO");
  }
}
