#include <bits/stdc++.h>
using namespace std;
inline long long gcd(long long x, long long y) {
  return (x % y == 0) ? y : gcd(y, x % y);
}
long long mul(long long x, long long y, long long MOD) {
  long long ans = 0;
  while (y) {
    if (y & 1) ans = (ans + x) % MOD;
    x = (x + x) % MOD;
    y >>= 1;
  }
  return ans;
}
long long pow_mod(long long x, long long k, long long MOD) {
  long long ans = 1;
  while (k) {
    if (k & 1) ans = mul(ans, x, MOD);
    x = mul(x, x, MOD);
    k >>= 1;
  }
  return ans;
}
long long fact[15];
int cnt;
namespace Math {
const int prime[15] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
bool is_prime(long long c, long long n) {
  long long d = n - 1;
  while (!(d & 1)) d >>= 1;
  long long t = pow_mod(c, d, n);
  while (d != n - 1 && t != 1 && t != n - 1) {
    t = mul(t, t, n);
    d <<= 1;
  }
  return (t == n - 1) || (d & 1);
}
bool miller_rabin(long long n) {
  for (int i = 0; i < 15; i++) {
    if (n == prime[i]) return 1;
    if (n % prime[i] == 0) return 0;
  }
  for (int i = 0; i < 10; i++) {
    long long c = rand() % (n - 2) + 2;
    if (!is_prime(c, n)) return 0;
  }
  return 1;
}
void pollard_rho(long long n) {
  if (miller_rabin(n)) {
    fact[++cnt] = n;
    return;
  }
  for (;;) {
    long long a, b, c;
    a = b = rand() % n;
    c = rand() % n;
    b = (mul(b, b, n) + c) % n;
    while (a != b) {
      long long t = gcd(abs(a - b), n);
      if (t != 1 && t != n) {
        pollard_rho(t);
        pollard_rho(n / t);
        return;
      }
      a = (mul(a, a, n) + c) % n;
      b = (mul(b, b, n) + c) % n;
      b = (mul(b, b, n) + c) % n;
    }
  }
}
}  // namespace Math
namespace Solve1 {
bool solve(long long n) {
  long long a = fact[1], b = fact[2];
  long long nev = mul(pow_mod(b % a, a - 2, a), n % a, a);
  return (b * nev <= n);
}
}  // namespace Solve1
namespace Solve2 {
priority_queue<pair<long long, int>, vector<pair<long long, int> >,
               greater<pair<long long, int> > >
    q;
long long dis[100005];
void dijkstra() {
  memset(dis, 0x3f, sizeof(dis));
  while (!q.empty()) q.pop();
  int p = fact[1];
  dis[0] = 0;
  q.push(pair<long long, int>(0, 0));
  while (!q.empty()) {
    pair<long long, int> t = q.top();
    q.pop();
    if (dis[t.second] < t.first) continue;
    int a = t.second;
    long long b = t.first;
    for (int i = 2; i <= cnt; i++)
      if (b + fact[i] < dis[(a + fact[i]) % p]) {
        int u = (a + fact[i]) % p;
        dis[u] = b + fact[i];
        q.push(pair<long long, int>(dis[u], u));
      }
  }
}
bool solve(long long n) { return dis[n % fact[1]] <= n; }
}  // namespace Solve2
bool ans[10005];
map<long long, int> mp;
vector<pair<long long, int> > vt[55];
long long num[10005];
int main() {
  int cases;
  scanf("%d", &cases);
  int tot = 0;
  for (int i = 1; i <= cases; i++) {
    long long n = 0, k = 0;
    scanf("%lld%lld", &n, &k);
    if (k == 1) continue;
    if (!mp.count(k)) {
      mp[k] = ++tot;
      num[tot] = k;
    }
    vt[mp[k]].push_back(pair<long long, int>(n, i));
  }
  for (int i = 1; i <= tot; i++) {
    cnt = 0;
    Math::pollard_rho(num[i]);
    sort(fact + 1, fact + cnt + 1);
    cnt = unique(fact + 1, fact + cnt + 1) - fact - 1;
    if (cnt == 1) {
      long long a = fact[1];
      for (int j = 0; j < vt[i].size(); j++)
        ans[vt[i][j].second] = (vt[i][j].first % a == 0);
    } else if (cnt == 2) {
      for (int j = 0; j < vt[i].size(); j++)
        ans[vt[i][j].second] = Solve1::solve(vt[i][j].first);
    } else {
      Solve2::dijkstra();
      for (int j = 0; j < vt[i].size(); j++)
        ans[vt[i][j].second] = Solve2::solve(vt[i][j].first);
    }
  }
  for (int i = 1; i <= cases; i++) puts((ans[i]) ? "YES" : "NO");
  return 0;
}
