#include <bits/stdc++.h>
using namespace std;
bool np[33000000], inq[100010], b;
long long n, k, dis[55][100010], p[55][33000000 / 15 / 6];
int prime[33000000 / 15], num, cnt[55], now, total;
queue<int> q;
map<long long, int> mp;
inline int getint() {
  char c = getchar();
  int x;
  bool p;
  x = p = 0;
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') p = 1, c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  if (p) x = -x;
  return x;
}
inline long long getll() {
  char c = getchar();
  long long x;
  bool p;
  x = p = 0;
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') p = 1, c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  if (p) x = -x;
  return x;
}
void prepare() {
  total = num = 0;
  memset(np, 0, sizeof(np));
  for (int i = 2; i < 33000000; ++i) {
    if (!np[i]) prime[++num] = i;
    for (int j = 1; j <= num; ++j) {
      int tmp = i * prime[j];
      if (tmp >= 33000000) break;
      np[tmp] = 1;
      if (!(i % prime[j])) break;
    }
  }
}
void init() {
  n = getll(), k = getll();
  b = 0;
  if (mp.count(k))
    now = mp[k], b = 1;
  else
    now = ++total, mp[k] = now;
  if (b) return;
  long long tmp = k;
  cnt[now] = 0;
  for (int i = 1; 1ll * prime[i] * prime[i] <= k; ++i)
    if (!(tmp % prime[i])) {
      p[now][++cnt[now]] = prime[i];
      while (!(tmp % prime[i])) tmp /= prime[i];
    }
  if (tmp > 1) p[now][++cnt[now]] = tmp;
}
inline void spfa() {
  memset(dis[now], 127, sizeof(dis[now]));
  memset(inq, 0, sizeof(inq));
  dis[now][0] = 0;
  inq[0] = 1;
  q.push(0);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 2; i <= cnt[now]; ++i) {
      int v = (u + p[now][i]) % p[now][1];
      if (dis[now][v] > dis[now][u] + p[now][i]) {
        dis[now][v] = dis[now][u] + p[now][i];
        if (!inq[v]) inq[v] = 1, q.push(v);
      }
    }
    inq[u] = 0;
  }
}
inline void exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, x, y);
  long long tmp = x;
  x = y, y = tmp - a / b * y;
}
void solve() {
  if (!cnt[now]) {
    printf("NO\n");
    return;
  }
  if (cnt[now] == 1) {
    if (!(n % p[now][1])) {
      printf("YES\n");
      return;
    }
    printf("NO\n");
    return;
  }
  if (cnt[now] == 2) {
    long long x, y;
    exgcd(p[now][1], p[now][2], x, y);
    y = (y % p[now][1] + p[now][1]) % p[now][1];
    long long tmp = y * (n % p[now][1]) % p[now][1] * p[now][2];
    if (tmp <= n)
      printf("YES\n");
    else
      printf("NO\n");
    return;
  }
  if (!b) spfa();
  if (dis[now][n % p[now][1]] <= n)
    printf("YES\n");
  else
    printf("NO\n");
}
int main() {
  prepare();
  int t = getint();
  while (t--) {
    init();
    solve();
  }
  return 0;
}
