#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3fll;
const long long M = 1e9 + 7;
const long long maxn = 3e6 + 7;
const double pi = acos(-1.0);
const double eps = 0.00000001;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline T powMM(T a, T b) {
  T ret = 1;
  for (; b; b >>= 1ll, a = (long long)a * a % M)
    if (b & 1) ret = (long long)ret * a % M;
  return ret;
}
template <typename T>
inline T powMM(T a, T b, T M) {
  T ret = 1;
  for (; b; b >>= 1ll, a = (long long)a * a % M)
    if (b & 1) ret = (long long)ret * a % M;
  return ret;
}
const int maxsqrtk = 3.5e7 + 7;
int p[maxsqrtk], cntp;
void initfactor() {
  int i, j;
  for (i = 2; i < maxsqrtk; i++) {
    if (!p[i]) p[cntp++] = i;
    for (j = 0; j < cntp; j++) {
      if (i * p[j] >= maxsqrtk) break;
      p[i * p[j]] = 1;
      if (i % p[j] == 0) break;
    }
  }
  fprintf(stderr, "cnt_prime=%d\n", cntp);
}
const int maxk = 57;
vector<long long> minvalue[maxk], factor[maxk];
long long kth[maxk], cntk;
priority_queue<pair<long long, long long>, vector<pair<long long, long long> >,
               less<pair<long long, long long> > >
    Q;
int TaskA() {
  int i, id;
  long long n, k;
  scanf("%I64d%I64d", &n, &k);
  for (id = 0; id < cntk; id++)
    if (kth[id] == k) break;
  if (cntk == id) {
    fprintf(stderr, "%s\n", "initialize");
    kth[cntk++] = k;
    for (i = 0; i < cntp; i++) {
      if (p[i] > k / p[i]) break;
      if (k % p[i] == 0) factor[id].push_back(p[i]);
      while (k % p[i] == 0) k /= p[i];
    }
    if (k != 1) factor[id].push_back(k);
    if (factor[id].size() > 2) {
      long long p = factor[id][0];
      minvalue[id].resize(p, INFF);
      minvalue[id][0] = 0;
      Q.push(make_pair(0ll, 0ll));
      while (Q.size()) {
        auto now = Q.top();
        Q.pop();
        long long pos = now.second;
        if (minvalue[id][pos] != now.first) continue;
        for (long long len : factor[id])
          if (len != p) {
            long long nxtpos = (pos + len) % p,
                      nxtlen = minvalue[id][pos] + len;
            if (minvalue[id][nxtpos] > nxtlen) {
              minvalue[id][nxtpos] = nxtlen;
              Q.push(make_pair(minvalue[id][nxtpos], nxtpos));
            }
          }
      }
    }
  }
  if (factor[id].size() == 0) {
    return 0 * puts("NO");
  }
  if (factor[id].size() == 1) {
    if (n % factor[id][0] == 0)
      return 0 * puts("YES");
    else
      return 0 * puts("NO");
  }
  if (factor[id].size() == 2) {
    long long inv, a, p1 = factor[id][0], p2 = factor[id][1];
    inv = powMM(p1, p2 - 2, p2);
    a = n % p2 * inv % p2;
    if (a * p1 <= n)
      return 0 * puts("YES");
    else
      return 0 * puts("NO");
  } else {
    if (minvalue[id][n % factor[id][0]] <= n)
      return 0 * puts("YES");
    else
      return 0 * puts("NO");
  }
}
int main() {
  int startTime = clock();
  initfactor();
  fprintf(stderr, "/--- initializeTime: %d milliseconds ---/\n",
          clock() - startTime);
  int T = 1;
  scanf("%d", &T);
  startTime = clock();
  while (T--) TaskA();
  fprintf(stderr, "/--- computeTime: %d milliseconds ---/\n",
          clock() - startTime);
}
