// 同余最短路 Dijkstra 算法
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,int>
using namespace std;

const int N=100010,M=3.5e7;
bool comp[M]; vector<int>prim;
ll n,k,p[N],cnt,d[N];
map<ll,vector<pair<ll,int>> >mp;
int ans[N];

void Euler(){ //欧拉筛法
  for(int i=2;i<=M;i++){
    if(!comp[i]) prim.push_back(i);
    for(int j=0;j<prim.size()&&i*prim[j]<=M;j++){
      comp[i*prim[j]]=true;
      if(i%prim[j]==0) break;
    }
  }
}
ll qsm(ll a,ll b,ll p){ //快速幂
  ll res=1; 
  while(b){
    if(b&1) res=(res*a)%p;
    b>>=1;
    a=(a*a)%p;
  }
  return res;
}
void dijkstra(){
  for(int i=0;i<p[1];i++)d[i]=2e18; d[0]=0;
  priority_queue<pii,vector<pii>,greater<pii> > q; 
  q.push({0,0});
  while(!q.empty()){
    auto [dd,u]=q.top(); q.pop();
    if(dd!=d[u])continue;
    for(int i=2;i<=cnt;i++){ //枚举其它质因子
      int v=(u+p[i])%p[1];
      if(d[v]>d[u]+p[i]){
        d[v]=d[u]+p[i]; //最短路
        q.push({d[v],v});
      }
    }
  }
}
int main(){
  Euler();
  int t; scanf("%d",&t);
  for(int i=1;i<=t;i++){
    scanf("%lld%lld",&n,&k);
    mp[k].push_back({n,i}); //离线保存，k<=50，每个k有多个不同的n
  }
  for(auto [fir,sec]:mp){ //离线处理，最多50次
    cnt=0; k=fir;
    if(k==1) continue;
    for(int i=0;i<prim.size()&&1ll*prim[i]*prim[i]<=k;i++){ //分解质因数
      if(k%prim[i]==0){ //如果pi是k的质因子
        p[++cnt]=prim[i];
        while(k%prim[i]==0) k/=prim[i]; //除掉质因子pi
      }
    }
    if(k>1) p[++cnt]=k; //记录最大的质因子
    
    if(cnt==1){ //一个质因子
      for(auto [n,i]:sec){
        if(n%p[cnt]==0) ans[i]=1; //如果n是质因子的倍数
        else ans[i]=0;
      }
    }
    else if(cnt==2){ //两个质因子(均>1e7时不能用最短路)
      for(auto [n,i]:sec){
        if(n%p[1]==0||n%p[2]==0){ //如果n是质因子的倍数
          ans[i]=1;
          continue;
        }
        ll a=p[1],b=p[2];
        if((n%a*qsm(b,a-2,a)%a)*b<=n) ans[i]=1; //例如 n=29,a=5,b=7
        else ans[i]=0;
      }
    }
    else{ //多个质因子
      dijkstra(); //同余最短路
      for(auto [n,i]:sec){
        if(d[n%p[1]]<=n) ans[i]=1; //如果n>=能被质因子拼出的最小数，那么n能被拼出
        else ans[i]=0;
      }
    }
  }
  for(int i=1;i<=t;i++) printf("%s\n",ans[i]?"YES":"NO");
}