#include <bits/stdc++.h>
const int N = 32000010;
const int M = 10010;
int min[N];
int prime[2000010], pcnt;
bool ans[M];
bool dp[N];
void init() {
  for (int i = 2; i < N; ++i) {
    if (!min[i]) {
      min[i] = i;
      prime[pcnt++] = i;
    }
    for (int j = 0; j < pcnt && i * prime[j] < N; ++j) {
      min[i * prime[j]] = prime[j];
      if (i % prime[j] == 0) {
        break;
      }
    }
  }
}
long long ex_euc(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  }
  long long ret = ex_euc(b, a % b, x, y), tmp = y;
  y = x - a / b * y;
  x = tmp;
  return ret;
}
long long inv(long long a, long long moder) {
  long long b = moder, s = 1, t = 0;
  while (b) {
    long long tmp = a, q = a / b;
    a = b, b = tmp % a;
    tmp = s;
    s = t;
    t = tmp - s * q;
  }
  return s < 0 ? s + moder : s;
}
long long divide(long long a, long long b) {
  return a / b - ((a ^ b) < 0 && a % b);
}
bool check(long long u, long long v, long long x, long long y, long long n) {
  return divide(-n * x + v - 1, v) <= divide(n * y, u);
}
int main() {
  init();
  int test;
  scanf("%d", &test);
  std::map<long long, std::vector<std::pair<long long, int>>> map;
  for (int i = 0; i < test; ++i) {
    long long n, k;
    scanf("%lld%lld", &n, &k);
    map[k].push_back({n, i});
  }
  for (auto &u : map) {
    long long k = u.first;
    std::vector<long long> prime;
    long long x = k;
    for (int i = 0; i < pcnt; ++i) {
      if (x % ::prime[i] == 0) {
        prime.push_back(::prime[i]);
        while (x % ::prime[i] == 0) {
          x /= ::prime[i];
        }
      }
    }
    if (x > 1) {
      prime.push_back(x);
    }
    if (prime.size() >= 4) {
      int sz = prime[0] * prime[1];
      memset(dp, 0, sizeof(bool) * sz);
      dp[0] = true;
      for (auto v : prime) {
        for (int i = 0; i + v < sz; ++i) {
          if (dp[i]) dp[i + v] = true;
        }
      }
      for (auto v : u.second) {
        ans[v.second] = v.first >= sz ? true : dp[v.first];
      }
      continue;
    }
    if (prime.empty()) {
      for (auto v : u.second) {
        ans[v.second] = false;
      }
      continue;
    }
    if (prime.size() == 1) {
      for (auto v : u.second) {
        ans[v.second] = !(v.first % prime[0]);
      }
      continue;
    }
    if (prime.size() == 2) {
      for (auto v : u.second) {
        long long n = v.first;
        if (n >= prime[0] * prime[1]) {
          ans[v.second] = true;
          continue;
        }
        long long t = (n % prime[0]) * inv(prime[1], prime[0]) % prime[0];
        ans[v.second] = n - t * prime[1] >= 0;
      }
      continue;
    }
    long long uu = prime[0], vv = prime[1];
    long long y;
    ex_euc(uu, vv, x, y);
    for (auto v : u.second) {
      long long n = v.first;
      if (n >= uu * vv) {
        ans[v.second] = true;
        continue;
      }
      ans[v.second] = false;
      for (int i = 0; i * prime[2] <= n; ++i) {
        if (check(uu, vv, x, y, n - i * prime[2])) {
          ans[v.second] = true;
          break;
        }
      }
    }
  }
  for (int i = 0; i < test; ++i) {
    puts(ans[i] ? "YES" : "NO");
  }
  return 0;
}
