#include <bits/stdc++.h>
using namespace std;
template <typename T>
void maxtt(T &t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T &t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "Yes" : "No");
  exit(0);
}
void addmod(int &x, int y, int mod = 1000000007) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et() {
  puts("-1");
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 1000000007) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
const int N = 32000000;
bitset<N + 5> bs;
vector<int> ps;
vector<long long> pks;
bool Ans[100005];
long long extend_gcd(long long a, long long b, long long &x, long long &y,
                     long long d) {
  if (b == 0) {
    x = d / a;
    y = 0;
    return a;
  } else {
    long long r = extend_gcd(b, a % b, y, x, d);
    y -= x * (a / b);
    return r;
  }
}
void init() {
  ps.push_back(2);
  for (int i = 3; i <= N; i += 2)
    if (!bs[i]) {
      ps.push_back(i);
      for (int j = i + i; j <= N; j += i) {
        bs[j] = 1;
      }
    }
}
long long p1, p2, G, pg1, pg2;
long long dis[100005];
bool used[100005];
void dij() {
  for (int(i) = 0; (i) < (int)(p1); (i)++) {
    dis[i] = (1LL << 60);
    used[i] = 0;
  }
  dis[0] = 0;
  priority_queue<pair<long long, int>, std::vector<pair<long long, int>>,
                 std::greater<pair<long long, int>>>
      q;
  q.push({0, 0});
  while (!q.empty()) {
    int x = q.top().second;
    q.pop();
    if (used[x]) continue;
    used[x] = 1;
    for (auto p : pks) {
      long long d = p;
      int y = (x + p) % p1;
      if (dis[x] + d < dis[y]) {
        dis[y] = dis[x] + d;
        q.push({dis[y], y});
      }
    }
  }
}
void reinitK(long long k) {
  pks.clear();
  long long tk = k;
  for (int P : ps) {
    if ((long long)P * P > tk) break;
    if (tk % P == 0) {
      pks.push_back(P);
      while (tk % P == 0) tk /= P;
    }
  }
  if (tk != 1) pks.push_back(tk);
  if (pks.size() == 2) {
    p1 = pks[0];
    p2 = pks[1];
    G = gcd1(p1, p2);
    pg1 = p1 / G;
    pg2 = p2 / G;
  } else if (pks.size() > 2) {
    p1 = pks[0];
    dij();
  }
}
long long qn[100005], qk[100005];
void fmain(int ID) {
  init();
  scanf("%d", &n);
  long long pk = -1;
  vector<pair<long long, int>> vp;
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    scanf("%lld%lld", qn + i, qk + i);
    vp.push_back({qk[i], i});
  }
  sort(vp.begin(), vp.end());
  for (int(i) = 0; (i) < (int)(n); (i)++) {
    int id = vp[i].second;
    if (qk[id] != pk) {
      reinitK(qk[id]);
      pk = qk[id];
    }
    if (qk[id] == 1)
      Ans[id] = 0;
    else if (pks.size() == 1)
      Ans[id] = qn[id] % pks[0] == 0;
    else if (pks.size() == 2) {
      if (qn[id] % G != 0) {
        Ans[id] = 0;
        continue;
      }
      long long x, y;
      extend_gcd(p1, p2, x, y, G);
      x %= pg2;
      if (x < 0) x += pg2;
      Ans[id] = ((qn[id] % p2) * x % p2) * p1 <= qn[id];
    } else {
      Ans[id] = dis[qn[id] % p1] <= qn[id];
    }
  }
  for (int(i) = 1; (i) <= (int)(n); (i)++) puts(Ans[i] ? "YES" : "NO");
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}
