#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 3.3e7;
int prm[M], tot;
void init(int n) {
  for (int i = 2; i <= n; i++) {
    if (!prm[i]) prm[++tot] = i;
    for (int j = 1; j <= tot && i * prm[j] <= n; ++j) {
      prm[i * prm[j]] = true;
      if (i % prm[j] == 0) break;
    }
  }
}
struct Query {
  long long n, k;
  int id;
  bool operator<(const Query& A) const { return k < A.k; }
} Q[N];
bool ans[N];
int m;
long long fac[N];
void exgcd(long long a, long long b, long long& x, long long& y) {
  if (!b)
    assert(a == 1), x = 1, y = 0;
  else {
    exgcd(b, a % b, y, x);
    y -= a / b * x;
  }
}
void work(long long a, long long b, int l, int r) {
  long long x, y;
  exgcd(a, b, x, y);
  y = (y % a + a) % a;
  for (int i = l; i <= r; i++) {
    long long val = (y * (Q[i].n % a)) % a * b;
    ans[Q[i].id] = val <= Q[i].n;
  }
}
bool vis[N];
long long dis[N];
struct Node {
  int o;
  long long d;
  bool operator<(const Node& B) const { return d > B.d; }
};
void Dijkstra() {
  int n = fac[1];
  for (int i = 0; i <= n; i++) dis[i] = 1ll << 60, vis[i] = 0;
  dis[0] = 0;
  priority_queue<Node> q;
  q.push((Node){0, 0});
  while (!q.empty()) {
    int o = q.top().o;
    q.pop();
    if (vis[o]) continue;
    vis[o] = true;
    for (int i = 2; i <= m; i++) {
      long long d = dis[o] + (o + fac[i]) / n;
      int u = (o + fac[i]) % n;
      if (dis[u] > d) dis[u] = d, q.push((Node){u, d});
    }
  }
}
int main() {
  init(M - 5);
  int q;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++)
    scanf("%I64d%I64d", &Q[i].n, &Q[i].k), Q[i].id = i;
  sort(Q + 1, Q + q + 1);
  for (int i = 1; i <= q; i++) {
    long long x = Q[i].k;
    int r = i;
    while (r < q && Q[r + 1].k == x) ++r;
    m = 0;
    for (int j = 1; j <= tot; j++)
      if (x % prm[j] == 0) {
        fac[++m] = prm[j];
        while (x % prm[j] == 0) x /= prm[j];
      }
    if (x > 1) fac[++m] = x;
    if (m == 0)
      for (int j = i; j <= r; j++) ans[Q[j].id] = false;
    else if (m == 1)
      for (int j = i; j <= r; j++) ans[Q[j].id] = Q[j].n % fac[1] == 0;
    else if (m == 2)
      work(fac[1], fac[2], i, r);
    else {
      Dijkstra();
      for (int j = i; j <= r; j++)
        ans[Q[j].id] = dis[Q[j].n % fac[1]] <= Q[j].n / fac[1];
    }
    i = r;
  }
  for (int i = 1; i <= q; i++) puts(ans[i] ? "YES" : "NO");
  return 0;
}
