#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int T, tot, p[3000010];
long long n, k, dist[maxn];
bool ok[35000000], ans[maxn];
map<long long, vector<pair<long long, int> > > mp;
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, y, x), y -= a / b * x;
}
void solve(long long k, vector<pair<long long, int> > Q) {
  vector<long long> a;
  for (long long i = 1; i <= tot; i++) {
    if (k % p[i] == 0) {
      a.push_back(p[i]);
      while (k % p[i] == 0) k /= p[i];
    }
  }
  if (k > 1) a.push_back(k);
  int n = a.size();
  if (n == 0) return;
  if (n == 1) {
    for (auto q : Q) ans[q.second] = q.first % a[0] == 0;
    return;
  }
  if (n == 2) {
    long long x, y;
    exgcd(a[0], a[1], x, y), y = (y % a[0] + a[0]) % a[0];
    for (auto q : Q)
      ans[q.second] = y * (q.first % a[0]) % a[0] * a[1] <= q.first;
    return;
  }
  int m = a[0];
  for (int i = 0; i < m; i++) dist[i] = 2e18;
  dist[0] = 0;
  set<pair<int, long long> > S;
  for (int i = 0; i < m; i++) S.insert(make_pair(dist[i], i));
  while (!S.empty()) {
    int v = S.begin()->second;
    S.erase(S.begin());
    for (int i = 1; i < n; i++) {
      int u = (v + a[i]) % m;
      long long w = dist[v] + a[i];
      if (dist[u] <= w) continue;
      S.erase(make_pair(dist[u], u)), S.insert(make_pair(dist[u] = w, u));
    }
  }
  for (auto q : Q) ans[q.second] = dist[q.first % m] <= q.first;
}
int main() {
  for (int i = 2; i < 35000000; i++) {
    if (ok[i]) continue;
    p[++tot] = i;
    for (int j = i + i; j < 35000000; j += i) ok[j] = 1;
  }
  scanf("%d", &T);
  for (int i = 0; i < T; i++) {
    scanf("%lld %lld", &n, &k), mp[k].push_back(make_pair(n, i));
  }
  for (auto it : mp) solve(it.first, it.second);
  for (int i = 0; i < T; i++) printf("%s\n", ans[i] ? "YES" : "NO");
  return 0;
}
