#include <bits/stdc++.h>   template <typename T>   inline void read(T &x) {     x = 0;     char c = getchar();     while (!isdigit(c)) c = getchar();     while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();   }   using namespace std;   int t;   int pri[4001000], pcnt;   bool depri[35001000];   inline void init() {     depri[1] = true;     const int up = 3.5e7;     for (int i = 2; i <= up; ++i) {       if (!depri[i]) pri[++pcnt] = i;       for (int j = 1; j <= pcnt && i * pri[j] <= up; ++j) {         depri[i * pri[j]] = true;         if (i % pri[j] == 0) break;       }     }   }   struct TC {     int id;     long long n, k;     inline bool operator<(const TC &a) const { return k < a.k; }   } tc[10100];   bool ans[10100];   long long p[100];   int ptot;   inline void Div(long long x) {     ptot = 0;     for (int i = 1; 1ll * pri[i] * pri[i] <= x; ++i) {       if (x % pri[i] == 0) {         p[++ptot] = pri[i];         while (x % pri[i] == 0) x /= pri[i];       }     }     if (x != 1) p[++ptot] = x;   }   struct node {     int cur;     long long val;     inline bool operator<(const node &a) const { return val > a.val; }   };   priority_queue<node> q;   long long dis[100100];   bool vis[100100];   inline void Update(long long k) {     Div(k);     if (ptot <= 2) return;     memset(dis, 0x3f, sizeof(dis));     memset(vis, 0, sizeof(vis));     dis[0] = 0;     q.push((node){0, 0});     while (!q.empty()) {       int cur = (q.top()).cur;       q.pop();       if (vis[cur]) continue;       vis[cur] = true;       for (int i = 2; i <= ptot; ++i) {         int to = (cur + p[i]) % p[1];         long long val = (cur + p[i]) / p[1];         if (dis[to] <= dis[cur] + val) continue;         dis[to] = dis[cur] + val;         q.push((node){to, dis[to]});       }     }   }   inline long long quickmul(long long x, long long k, long long P) {     x = (x % P + P) % P;     k = (k % P + P) % P;     long long res = 0;     while (k) {       if (k & 1) res = (res + x) % P;       x = (x + x) % P;       k >>= 1;     }     return res;   }   long long exgcd(long long a, long long b, long long &x, long long &y) {     if (!b) {       x = 1;       y = 0;       return a;     }     long long g = exgcd(b, a % b, x, y);     long long tmp = x;     x = y;     y = tmp - a / b * y;     return g;   }   inline bool get_ans(long long n) {     if (!ptot) return false;     if (ptot == 1) return n % p[1] == 0;     if (ptot == 2) {       long long x = 0, y = 1;       exgcd(p[1], p[2], x, y);       x = quickmul(x, n, p[2]);       if (1.0 * x * p[1] > 2e18) return false;       return n >= x * p[1];     }     if (1.0 * dis[n % p[1]] * p[1] > 2e18) return false;     return dis[n % p[1]] * p[1] + n % p[1] <= n;   }   signed main() {     init();     read(t);     for (int i = 1; i <= t; ++i) {       read(tc[i].n), read(tc[i].k);       tc[i].id = i;     }     sort(tc + 1, tc + 1 + t);     for (int i = 1; i <= t; ++i) {       if (tc[i].k != tc[i - 1].k) Update(tc[i].k);       ans[tc[i].id] = get_ans(tc[i].n);     }     for (int i = 1; i <= t; ++i) puts(ans[i] ?  YES  :  NO );     return 0;   }   