#include <bits/stdc++.h>
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
}
using namespace std;
int t;
int pri[4001000], pcnt;
bool depri[35001000];
inline void init() {
  depri[1] = true;
  const int up = 3.5e7;
  for (int i = 2; i <= up; ++i) {
    if (!depri[i]) pri[++pcnt] = i;
    for (int j = 1; j <= pcnt && i * pri[j] <= up; ++j) {
      depri[i * pri[j]] = true;
      if (i % pri[j] == 0) break;
    }
  }
}
struct TC {
  int id;
  long long n, k;
  inline bool operator<(const TC &a) const { return k < a.k; }
} tc[10100];
bool ans[10100];
long long p[100];
int ptot;
inline void Div(long long x) {
  ptot = 0;
  for (int i = 1; 1ll * pri[i] * pri[i] <= x; ++i) {
    if (x % pri[i] == 0) {
      p[++ptot] = pri[i];
      while (x % pri[i] == 0) x /= pri[i];
    }
  }
  if (x != 1) p[++ptot] = x;
}
struct node {
  int cur;
  long long val;
  inline bool operator<(const node &a) const { return val > a.val; }
};
priority_queue<node> q;
long long dis[100100];
bool vis[100100];
inline void Update(long long k) {
  Div(k);
  if (ptot <= 2) return;
  memset(dis, 0x3f, sizeof(dis));
  memset(vis, 0, sizeof(vis));
  dis[0] = 0;
  q.push((node){0, 0});
  while (!q.empty()) {
    int cur = (q.top()).cur;
    q.pop();
    if (vis[cur]) continue;
    vis[cur] = true;
    for (int i = 2; i <= ptot; ++i) {
      int to = (cur + p[i]) % p[1];
      long long val = (cur + p[i]) / p[1];
      if (dis[to] <= dis[cur] + val) continue;
      dis[to] = dis[cur] + val;
      q.push((node){to, dis[to]});
    }
  }
}
inline long long quickmul(long long x, long long k, long long P) {
  x = (x % P + P) % P;
  k = (k % P + P) % P;
  long long res = 0;
  while (k) {
    if (k & 1) res = (res + x) % P;
    x = (x + x) % P;
    k >>= 1;
  }
  return res;
}
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  long long g = exgcd(b, a % b, x, y);
  long long tmp = x;
  x = y;
  y = tmp - a / b * y;
  return g;
}
inline bool get_ans(long long n) {
  if (!ptot) return false;
  if (ptot == 1) return n % p[1] == 0;
  if (ptot == 2) {
    long long x = 0, y = 1;
    exgcd(p[1], p[2], x, y);
    x = quickmul(x, n, p[2]);
    if (1.0 * x * p[1] > 2e18) return false;
    return n >= x * p[1];
  }
  if (1.0 * dis[n % p[1]] * p[1] > 2e18) return false;
  return dis[n % p[1]] * p[1] + n % p[1] <= n;
}
signed main() {
  init();
  read(t);
  for (int i = 1; i <= t; ++i) {
    read(tc[i].n), read(tc[i].k);
    tc[i].id = i;
  }
  sort(tc + 1, tc + 1 + t);
  for (int i = 1; i <= t; ++i) {
    if (tc[i].k != tc[i - 1].k) Update(tc[i].k);
    ans[tc[i].id] = get_ans(tc[i].n);
  }
  for (int i = 1; i <= t; ++i) puts(ans[i] ? "YES" : "NO");
  return 0;
}
