#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = 4e7 + 5;
long long n, k;
map<long long, int> IM;
int tot = 0;
vector<long long> s[N];
int ID(long long x) {
  if (IM.count(x)) return IM[x];
  IM[x] = ++tot;
  return -1;
}
int p[M], cnt;
bool vis[M];
void init() {
  for (int i = (2); i < (M - 2); i++) {
    if (!vis[i]) p[cnt++] = i;
    for (int j = 0; j < cnt && (long long)p[j] * i < M; j++) {
      vis[p[j] * i] = true;
      if (i % p[j] == 0) break;
    }
  }
}
vector<pair<int, long long> > g[N];
long long d[60][N];
void dij(long long *d) {
  priority_queue<pair<int, long long>, vector<pair<int, long long> >,
                 greater<pair<int, long long> > >
      q;
  d[0] = 0;
  q.push(pair<int, long long>(0, 0));
  while (!q.empty()) {
    int u = q.top().second;
    q.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (auto it : g[u]) {
      if (d[u] + it.second < d[it.first]) {
        d[it.first] = d[u] + it.second;
        q.push(pair<int, long long>(d[it.first], it.first));
      }
    }
  }
}
long long qpow(long long x, long long n, long long p) {
  long long res = 1;
  while (n > 0) {
    if (n & 1) res = res * x % p;
    x = x * x % p;
    n >>= 1;
  }
  return res;
}
int main() {
  init();
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%I64d%I64d", &n, &k);
    if (n == 1 || k == 1) {
      printf("NO\n");
      continue;
    }
    int id = ID(k);
    if (id == -1) {
      id = tot;
      long long tmp = k;
      for (int i = 0; (long long)p[i] * p[i] <= tmp; i++) {
        if (tmp % p[i] == 0) {
          while (tmp % p[i] == 0) tmp /= p[i];
          s[id].push_back(p[i]);
        }
      }
      if (tmp > 1) s[id].push_back(tmp);
      if ((int)s[id].size() >= 3) {
        int mn = s[id][0];
        for (int i = (0); i < (mn); i++)
          g[i].clear(), vis[i] = false, d[id][i] = 2e18;
        for (int i = (0); i < (mn); i++)
          for (auto v : s[id])
            g[i].push_back(pair<int, long long>((v + i) % mn, v));
        dij(d[id]);
      }
    }
    if ((int)s[id].size() == 1) {
      if (n % s[id][0] == 0)
        printf("YES\n");
      else
        printf("NO\n");
    } else if ((int)s[id].size() == 2) {
      long long inv1 = qpow(s[id][0], s[id][1] - 2, s[id][1]);
      long long b = n % s[id][1] * inv1 % s[id][1];
      if (b == 0 || n / b >= s[id][0]) {
        printf("YES\n");
      } else
        printf("NO\n");
    } else if ((int)s[id].size() >= 3) {
      int mn = s[id][0];
      if (d[id][(n % mn)] <= n)
        printf("YES\n");
      else
        printf("NO\n");
    }
  }
  return 0;
}
