#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("avx")
#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
template <typename T>
int sgn(T val) {
  return (T(0) < val) - (val < T(0));
}
long long read() {
  long long x = 0;
  bool q = 0;
  char c = getchar();
  while (!isdigit(c)) q |= (c == '-'), c = getchar();
  while (isdigit(c)) x = (x << 1) + (x << 3) + c - '0', c = getchar();
  return q ? -x : x;
}
void print(long long x, char q = '\n') {
  if (x < 0) putchar('-'), x = -x;
  if (x == 0) putchar('0');
  stack<char> s;
  s.push(q);
  while (x > 0) s.push(x % 10 + '0'), x /= 10;
  while (!s.empty()) putchar(s.top()), s.pop();
}
string read_s() {
  string s;
  char c = getchar();
  while (c == ' ' || c == '\t' || c == '\n') c = getchar();
  while (c != ' ' && c != '\t' && c != '\n') s += c, c = getchar();
  return s;
}
void print_s(string s, char q = '\n') {
  for (char c : s) putchar(c);
  putchar(q);
}
char read_c() {
  char c = getchar();
  while (c == ' ' || c == '\t' || c == '\n') c = getchar();
  return c;
}
long long mul(long long a, long long b, long long mod) {
  bool q = (a < 0) ^ (b < 0);
  a = abs(a) % mod, b = abs(b) % mod;
  long long ret = 0;
  while (b) {
    if (b & 1) {
      ret += a;
      if (ret >= mod) ret -= mod;
    }
    a += a;
    if (a >= mod) a -= mod;
    b >>= 1;
  }
  if (q) ret = (-ret) % mod;
  return ret;
}
long long ext_gcd(long long a, long long b, long long &x, long long &y) {
  long long xx = y = 0, yy = x = 1;
  while (b) {
    int q = a / b, t = b;
    b = a % b;
    a = t;
    t = xx;
    xx = x - q * xx;
    x = t;
    t = yy;
    yy = y - q * yy;
    y = t;
  }
  return a;
}
bool solve(long long a, long long b, long long c, long long &x, long long &y,
           long long &z) {
  z = ext_gcd(a, b, x, y);
  if (c % z != 0) return 0;
  long long dx = c / a;
  c -= dx * a;
  long long dy = c / b;
  c -= dy * b;
  x = dx + mul(x, c / z, b);
  y = dy + mul(y, c / z, a);
  z = abs(z);
  return 1;
}
const int MAX_N = 50000002;
vector<long long> a[204];
map<long long, int> pt;
map<long long, int> M;
bool pr[MAX_N];
int main() {
  int id = 0, idx = 60;
  for (int i = 2; i * i < MAX_N; i++) {
    if (!pr[i]) {
      for (int j = i * i; j < MAX_N; j += i) {
        pr[j] = 1;
      }
    }
  }
  vector<long long> p;
  for (int i = 2; i < MAX_N; i++)
    if (!pr[i]) p.push_back(i);
  int t = read();
  while (t--) {
    long long n = read(), k = read();
    if (k == 1) {
      puts("NO");
      continue;
    }
    int _;
    if (pt.count(k))
      _ = pt[k];
    else {
      _ = pt[k] = id;
      vector<long long> &z = a[id++];
      long long x = k;
      for (long long u : p)
        if (x % u == 0) {
          while (x % u == 0) x /= u;
          z.push_back(u);
        }
      if (x > 1) z.push_back(x);
    }
    vector<long long> z = a[_];
    if (z.size() == 1)
      puts(n % z.front() == 0 ? "YES" : "NO");
    else if (z.size() == 2) {
      long long x, y, w;
      if (!solve(z[0], z[1], n, x, y, w))
        puts("NO");
      else {
        z[0] /= w;
        z[1] /= w;
        if (x < 0) {
          x = -x;
          long long t = x / z[1] + (x % z[1] != 0 ? 1 : 0);
          if (y - z[0] * t < 0)
            puts("NO");
          else
            puts("YES");
        } else if (y < 0) {
          y = -y;
          long long t = y / z[0] + (y % z[0] != 0 ? 1 : 0);
          if (x - z[1] * t < 0)
            puts("NO");
          else
            puts("YES");
        } else {
          puts("YES");
        }
      }
    } else {
      if (n < z[0]) {
        puts("NO");
        continue;
      }
      if (M.count(k))
        _ = M[k];
      else {
        _ = M[k] = idx;
        vector<long long> &D = a[idx++];
        D.assign(z[0], (long long)2e18);
        D[0] = 0;
        map<long long, long long> q;
        q[0] = 0;
        while (q.size()) {
          long long x = (*q.begin()).first, d = (*q.begin()).second;
          q.erase(x);
          for (long long u : z) {
            long long xx = (x + u) % z[0], dd = d + u;
            if (dd > 2e18) continue;
            if (D[xx] > dd) D[xx] = q[xx] = dd;
          }
        }
      }
      vector<long long> &D = a[_];
      if (D[n % z[0]] > n)
        puts("NO");
      else
        puts("YES");
    }
  }
}
