#include <bits/stdc++.h>
using namespace std;
long long f[100100];
int pr[31600000], t, p[100100], l, que[100100 * 20], head, tail;
bool bz[31600000], ans[100100], vis[100100];
struct qry {
  long long n, k, w;
} q[100100];
bool cmp(qry a, qry b) { return a.k < b.k; }
long long qpow(long long a, long long i, long long mo) {
  long long r = 1;
  for (; i; i >>= 1, a = a * a % mo)
    if (i & 1) r = r * a % mo;
  return r;
}
int main() {
  scanf("%d", &t);
  for (int i = 1; i <= t; i++)
    scanf("%I64d%I64d", &q[i].n, &q[i].k), q[i].w = i;
  sort(q + 1, q + t + 1, cmp);
  for (int i = 2; i < 31600000; i++) {
    if (!bz[i]) pr[++pr[0]] = i;
    for (int j = 1; j <= pr[0] && i * pr[j] < 31600000; j++) {
      bz[i * pr[j]] = 1;
      if (i % pr[j] == 0) break;
    }
  }
  for (int i = 1; i <= t; i++) {
    long long n = q[i].n, k = q[i].k;
    if (k != q[i - 1].k) {
      l = 0;
      for (int j = 1; k > 1; j++) {
        if ((long long)pr[j] * pr[j] > k) {
          p[++l] = k;
          break;
        }
        if (k % (long long)pr[j] == 0) {
          p[++l] = pr[j];
          while (k % (long long)pr[j] == 0) k /= (long long)pr[j];
        }
      }
    }
    k = q[i].k;
    if (l == 0)
      ans[q[i].w] = 0;
    else if (l == 1)
      ans[q[i].w] = n % k == 0;
    else if (l == 2) {
      long long b =
          n % (long long)p[1] * qpow(p[2], p[1] - 2, p[1]) % (long long)p[1];
      ans[q[i].w] = b * (long long)p[2] <= n;
    } else {
      if (k != q[i - 1].k) {
        for (int j = 1; j <= p[1]; j++) f[j] = 1e18;
        f[0] = 0;
        for (head = 0, vis[que[tail = 1] = 0] = 1; head ^ tail;) {
          int x, j;
          for (x = que[++head], j = 2; j <= l; j++) {
            long long F = f[x] + p[j];
            int v = (x + p[j]) % p[1];
            if (F < f[v]) {
              f[v] = F;
              if (!vis[v]) vis[que[++tail] = v] = 1;
            }
          }
          vis[x] = 0;
        }
      }
      ans[q[i].w] = f[q[i].n % p[1]] <= q[i].n;
    }
  }
  for (int i = 1; i <= t; i++)
    if (ans[i])
      printf("YES\n");
    else
      printf("NO\n");
  return 0;
}
