#include <bits/stdc++.h>
using namespace std;
namespace SHENZHEBEI {
static const int GYN = 2333333;
char SZB[GYN], *SS = SZB, *TT = SZB;
inline char gc() {
  if (SS == TT) {
    TT = (SS = SZB) + fread(SZB, 1, GYN, stdin);
    if (SS == TT) return '\n';
  }
  return *SS++;
}
inline long long read() {
  long long x = 0, g = 1;
  char ch = gc();
  for (; !isdigit(ch); ch = gc())
    if (ch == '-') g = -1;
  for (; isdigit(ch); ch = gc()) x = x * 10 - 48 + ch;
  return x * g;
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
inline char readchar() {
  char ch = gc();
  for (; isspace(ch); ch = gc())
    ;
  return ch;
}
inline long long readstr(char *s) {
  char ch = gc();
  int cur = 0;
  for (; isspace(ch); ch = gc())
    ;
  for (; !isspace(ch); ch = gc()) s[cur++] = ch;
  s[cur] = '\0';
  return cur;
}
void Print(long long *a, int s, int t) {
  for (int i = (long long)(s); i <= (long long)(t); ++i) printf("%lld ", a[i]);
}
void Print(int *a, int s, int t) {
  for (int i = (long long)(s); i <= (long long)(t); ++i) printf("%d ", a[i]);
}
void Print(char *a, int s, int t) {
  for (int i = (long long)(s); i <= (long long)(t); ++i) putchar(a[i]);
}
void writeln(long long x) {
  write(x);
  puts("");
}
void Min(long long &x, long long y) { x = x < y ? x : y; }
void Max(long long &x, long long y) { x = x > y ? x : y; }
}  // namespace SHENZHEBEI
using namespace SHENZHEBEI;
const long long N = 500010;
struct dt {
  long long x, y, id;
} a[N];
bool mark[40000010];
long long TTT, q[1000], pri[8000010];
long long dis[200000], vis[200010], answ[200010];
priority_queue<pair<long long, long long>, vector<pair<long long, long long> >,
               greater<pair<long long, long long> > >
    Q;
bool cmp(dt a, dt b) { return a.y < b.y; }
void Init() {
  TTT = 40000000;
  for (int i = (long long)(2); i <= (long long)(TTT); ++i)
    if (!mark[i]) {
      pri[++pri[0]] = i;
      for (long long j = 2 * i; j <= TTT; j += i) mark[j] = 1;
    }
}
void FenJie(long long x) {
  q[0] = 0;
  for (long long i = 1; pri[i] * pri[i] <= x; ++i)
    if (!(x % pri[i])) {
      q[++q[0]] = pri[i];
      for (; !(x % pri[i]); x /= pri[i])
        ;
    }
  if (x > 1) q[++q[0]] = x;
}
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;
}
long long mul(long long a, long long b, long long mod) {
  long long ans = 0;
  for (; b; b >>= 1, a = (a + a) % mod)
    if (b & 1) ans = (ans + a) % mod;
  return ans;
}
int main() {
  long long T = read();
  Init();
  for (int i = (long long)(1); i <= (long long)(T); ++i) {
    long long x = read(), y = read();
    a[i] = (dt){x, y, i};
  }
  sort(a + 1, a + T + 1, cmp);
  for (long long i = 1, j; i <= T; i = j + 1) {
    j = i;
    for (; a[j + 1].y == a[i].y;) ++j;
    FenJie(a[j].y);
    if (a[j].y == 1) q[q[0] = 1] = 1e18 + 10000;
    if (q[0] == 1) {
      for (int k = (long long)(i); k <= (long long)(j); ++k) {
        answ[a[k].id] = a[k].x % q[1] ? 0 : 1;
      }
    } else if (q[0] == 2) {
      long long A = q[1], B = q[2], X, Y, XX, YY;
      exgcd(A, B, X, Y);
      X = (X % B + B) % B;
      exgcd(B, A, XX, YY);
      XX = (XX % A + A) % A;
      for (int k = (long long)(i); k <= (long long)(j); ++k) {
        long long n = a[k].x, x = n % A, y = n % B,
                  ans = mul(x * XX, B, (A * B)) + mul(y * X, A, (A * B));
        answ[a[k].id] = n < ans ? 0 : 1;
      }
    } else {
      memset(vis, 0, sizeof vis);
      memset(dis, 60, sizeof dis);
      dis[0] = 0;
      Q.push(make_pair(0, 0));
      for (; !Q.empty();) {
        long long x = Q.top().second;
        Q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (int j = (long long)(2); j <= (long long)(q[0]); ++j) {
          long long dist = dis[x] + q[j], to = dist % q[1];
          if (dis[to] > dist) {
            dis[to] = dist;
            Q.push(make_pair(dis[to], to));
          }
        }
      }
      dis[0] = q[1];
      for (int k = (long long)(i); k <= (long long)(j); ++k)
        answ[a[k].id] = dis[a[k].x % q[1]] <= a[k].x ? 1 : 0;
    }
  }
  for (int i = (long long)(1); i <= (long long)(T); ++i)
    puts(answ[i] ? "YES" : "NO");
}
