#include <bits/stdc++.h>
using namespace std;
const long long INF = 4e18;
const int BASE = 131;
const double eps = 1e-4;
const int mod = 998244353;
const int inf = 1061109567;
const double pi = acos(-1);
const int inv2 = (mod + 1) >> 1;
namespace Math {
inline long long popcount(long long x) {
  x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
  x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
  x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
  return x;
}
inline long long F(long long x, long long p) { return x >= p ? x - p : x; }
inline long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
inline long long ksm(long long x, long long t, long long p) {
  long long res = 1;
  while (t) {
    if (t & 1) res = 1LL * res * x % p;
    x = 1LL * x * x % p;
    t >>= 1;
  }
  return res;
}
}  // namespace Math
template <typename tp>
inline void read(tp &dig) {
  char ch = getchar();
  long long flag = 0;
  dig = 0;
  while (!isdigit(ch)) {
    if (ch == '-') flag = 1;
    ch = getchar();
  }
  while (isdigit(ch)) dig = dig * 10 + ch - '0', ch = getchar();
  if (flag) dig = -dig;
}
template <typename tp, typename... Args>
inline void read(tp &dig, Args &...args) {
  read(dig);
  read(args...);
}
struct node {
  long long n, k, id;
  inline bool operator<(const node &b) const { return k < b.k; }
} a[100010];
long long T, p[31], f[100010], vis[100010], ans[100010];
queue<int> que;
inline long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
inline long long mul(long long a, long long b, long long MOD) {
  return (a * b - (long long)((long double)a / MOD * b + 1e-6) * MOD + MOD) %
         MOD;
}
inline long long ksm(long long x, long long t, long long MOD) {
  long long res = 1;
  while (t) {
    if (t & 1) res = mul(res, x, MOD);
    x = mul(x, x, MOD);
    t >>= 1;
  }
  return res;
}
inline bool test(long long x, long long a, long long d) {
  while (!(d & 1)) d >>= 1;
  long long t = ksm(a, d, x);
  while ((d ^ (x - 1)) && t != x - 1 && t != 1) t = mul(t, t, x), d <<= 1;
  return t == x - 1 || (d & 1) == 1;
}
inline bool isprime(long long x) {
  if (x == 2 || x == 3 || x == 5 || x == 7 || x == 13) return true;
  if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0 || x % 13 == 0)
    return false;
  int a[] = {2, 3, 5, 7, 13};
  for (int i = 0; i <= 4; ++i)
    if (!test(x, a[i], x - 1)) return false;
  return true;
}
inline long long pollard_rho(long long n, long long c) {
  long long x = rand() % n + 1;
  if (x == 1) x += 3;
  while (x < n / x) x = x * x;
  x = (x % n + n) % n;
  long long y = x, i = 1, k = 2;
  while (true) {
    ++i;
    x = (mul(x, x, n) + c) % n;
    long long d = gcd(abs(y - x), n);
    if (1 < d && d < n) return d;
    if (y == x) return n;
    if (i == k) y = x, k <<= 1;
  }
}
inline long long find(long long x, long long c) {
  if (x == 1) return 0;
  if (isprime(x)) {
    p[++p[0]] = x;
    return 1;
  }
  long long p = x;
  while (p >= x) p = pollard_rho(p, c--);
  if (find(p, c)) return 1;
  if (find(x / p, c)) return 1;
}
int main() {
  read(T);
  srand(T);
  for (int i = 1; i <= T; ++i) read(a[i].n, a[i].k), a[i].id = i;
  sort(a + 1, a + T + 1);
  for (int i = 1; i <= T; ++i) {
    if (a[i].k ^ a[i - 1].k) {
      long long K = a[i].k;
      p[0] = 0;
      while (K ^ 1) {
        find(K, rand() % 51937 + 1);
        while (K % p[p[0]] == 0) K /= p[p[0]];
      }
    }
    if (!p[0]) {
      ans[a[i].id] = 0;
      continue;
    }
    if (p[0] == 1) {
      ans[a[i].id] = (a[i].n % a[i].k == 0);
      continue;
    }
    if (p[0] == 2) {
      long long b = a[i].n % p[1] * ksm(p[2], p[1] - 2, p[1]) % p[1];
      ans[a[i].id] = (b * p[2] <= a[i].n);
      continue;
    } else {
      if (a[i].k ^ a[i - 1].k) {
        sort(p + 1, p + p[0] + 1);
        for (int j = 1; j <= p[1]; ++j) f[j] = 1e18;
        que.push(0);
        vis[0] = 1;
        while (!que.empty()) {
          int now = que.front();
          que.pop();
          for (int j = 2; j <= p[0]; ++j) {
            int v = (now + p[j]) % p[1];
            if (f[now] + p[j] < f[v]) {
              f[v] = f[now] + p[j];
              if (!vis[v]) que.push(v), vis[v] = 1;
            }
          }
          vis[now] = 0;
        }
      }
      ans[a[i].id] = (f[a[i].n % p[1]] <= a[i].n);
    }
  }
  for (int i = 1; i <= T; ++i)
    if (ans[i])
      printf("YES\n");
    else
      printf("NO\n");
  return 0;
}
