#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, B = 32e6;
const long long inf = 1e17;
int p[N * 50], nump;
bool np[B + 5];
long long n, k, pr[105], cnt, d[N];
bool vis[N], ans[N];
struct data {
  long long n, k;
  int id;
} Q[N];
priority_queue<pair<long long, int> > q;
bool cmp(data a, data b) { return a.k < b.k; }
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 res = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return res;
}
void solve() {
  long long x = k;
  cnt = 0;
  for (int i = 1; 1ll * p[i] * p[i] <= x; ++i)
    if (x % p[i] == 0) {
      pr[++cnt] = p[i];
      while (x % p[i] == 0) x /= p[i];
    }
  if (x > 1) pr[++cnt] = x;
  if (cnt < 3) return;
  for (int i = (0); i <= (pr[1]); ++i) d[i] = inf, vis[i] = 0;
  d[0] = 0, q.push(make_pair(0, 0));
  while (!q.empty()) {
    int x = q.top().second;
    q.pop();
    if (vis[x]) continue;
    vis[x] = 1;
    for (int i = (2); i <= (cnt); ++i) {
      int v = (x + pr[i]) % pr[1];
      if (d[v] > d[x] + pr[i]) {
        d[v] = d[x] + pr[i], q.push(make_pair(-d[v], v));
      }
    }
  }
}
int main() {
  int T;
  scanf("%d", &T);
  np[1] = 1;
  for (int i = (2); i <= (B); ++i) {
    if (!np[i]) p[++nump] = i;
    for (int j = (1); j <= (nump); ++j) {
      if (1ll * i * p[j] > B) break;
      np[i * p[j]] = 1;
      if (i % p[j] == 0) break;
    }
  }
  for (int i = (1); i <= (T); ++i)
    scanf("%I64d%I64d", &Q[i].n, &Q[i].k), Q[i].id = i;
  sort(Q + 1, Q + T + 1, cmp);
  for (int i = (1); i <= (T); ++i) {
    n = Q[i].n, k = Q[i].k;
    if (i == 1 || k != Q[i - 1].k) solve();
    if (!cnt)
      ans[Q[i].id] = 0;
    else if (cnt == 1)
      ans[Q[i].id] = !(n % pr[1]);
    else if (cnt == 2) {
      long long a = pr[1], b = pr[2], x, y;
      exgcd(a, b, x, y);
      y = (y % a + a) % a, ans[Q[i].id] = (y * (n % a) % a * b <= n);
    } else
      ans[Q[i].id] = (d[n % pr[1]] <= n);
  }
  for (int i = (1); i <= (T); ++i) puts(ans[i] ? "YES" : "NO");
  return 0;
}
