#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define mx 10000000
#define SIZE 1000001

using namespace std;

int arr[SIZE];
bool status[mx];
/**************************************Seive************************************/
void seive()
{
    int N=mx;
    int sq=sqrt(N);
    for(int i=4; i<=N; i+=2) status[i]=1;
    for(int i=3; i<=sq; i+=2)
        if(!status[i])
            for(int j=i*i; j<=N; j+=2*i) status[j]=1;

    status[1]=1;
}


/**********************************Bitwise Seive*********************************/
//int N =100,prime[100];
//int status[100/32];
/*
bool Check(int N,int pos)
{
    return (bool)(N & (1<<pos));
}
int Set(int N,int pos)
{
    return N=N | (1<<pos);
}
void sieve()
{
    int i, j, sqrtN;
    sqrtN = int( sqrt( N ) );
    for( i = 3; i <= sqrtN; i += 2 )
    {
        if( Check(status[i/32],i%32)==0)
        {
            for( j = i*i; j <= N; j += 2*i )
            {
                status[j/32]=Set(status[j/32],j % 32)   ;
            }
        }
    }
    puts("2");
    for(i=3; i<=N; i+=2)
        if( Check(status[i/32],i%32)==0)
            printf("%d\n",i);

}
?/

/*********************************modPow*******************************/
ll modPow(ll b, ll e, ll m)
{
    ll res = 1;
    for (; e; e >>= 1, b = b*b%m) if (e & 1) res = res*b%m;
    return res;
}


/*********************************Segmented Seive*******************************/
int segmentedSieve ( int a, int b )///Returns number of primes between segment [a,b]
{
    if ( a == 1 ) a++;
    int sqrtn = sqrt ( b );
    memset ( arr, 0, sizeof arr ); ///Make all index of arr 0.

    vector<int>prime;
    seive();
    prime.push_back(2);
    for(int i=3; i<=1000000; i+=2)
        if(!status[i])prime.push_back(i);

    for ( int i = 0; i < prime.size() && prime[i] <= sqrtn; i++ )
    {
        int p = prime[i];
        int j = p * p;
        if ( j < a ) ///If j is smaller than a, then shift it inside of segment [a,b]
            j = ((a+p-1)/p)*p;
        for ( ; j <= b; j += p )
            arr[j-a] = 1; ///mark them as not prime
    }
    int res = 0;
    for ( int i = a; i <= b; i++ )
        if ( arr[i-a] == 0 ) res++;  ///If it is not marked, then it is a prime
    return res;
}


/**********************************Euler Function******************************/
int Euler(int n)
{
    int result = n;
    if(n%2==0) result -= result / 2;
    while (n % 2 == 0) n/=2;
    for(int i=3; i*i <= n; i+=2)
    {
        if (n % i == 0) result -= result / i;
        while (n % i == 0) n /= i;
    }
    if (n > 1) result -= result / n;
    return result;
}


/********************************No Of Divisor****************************/
ll Divisor(ll n)
{
    ll result = 1;
    ll p=1;
    while (n % 2 == 0)
    {
        n /= 2;
        p++;
    }
    result *= p;
    for(ll i=3; i*i <= n; i+=2)
    {
        p=1;
        while (n % i == 0)
        {
            n /= i;
            p++;
        }
        result *= p;
    }
    if (n > 1) result *= 2;
    return result;
}



/*************************************Mulmod**********************************/
long long mulmod(long long a,long long b,long long c)
{
    long long x = 0,y=a%c;
    while(b > 0)            /// this function calculates (a*b)%c taking into account
    {
        /// that a*b might overflow
        if(b&1 == 1)
        {
            x = (x+y)%c;
        }
        y = (y*2)%c;
        b >>= 1;///b /= 2
    }
    return x%c;
}



/*************************************BigMod**********************************/
ll bigmod(ll a,ll b,ll c)   ///If a,b int then this functon is enough
{
    ///else call mulmod function
    long long x=1,y=a;      /// long long is taken to avoid overflow of intermediate results
    while(b > 0)
    {
        if(b&1 == 1)///b%2==b&1
        {
            x=mulmod(x,y,c)%c;
            ///x=(x*y)%c;
        }
        y=mulmod(y,y,c)%c;
        ///y = (y*y)%c;
        b >>= 1;/// b /= 2
    }
    return x%c;
}



/************************Fermat’s Little Theorem******************************/
bool Fermat(ll p, ll iterations)///p the number which will be checked
{
    ///(a^(p-1))% p==1 ? prime : not prime;
    if(p == 1)  /// 1 isn't prime
        return false;
    for(int i=0; i<iterations; i++)
    {
        /// choose a random integer between 1 and p-1 ( inclusive )
        ll a = rand()%(p-1)+1;
        /// modulo is the function we developed above for modular exponentiation.
        if(bigmod(a,p-1,p) != 1)
            return false; ///* p is definitely composite */
    }
    return true; ///* p is probably prime */
}



/************************************Miller Test******************************/
bool Miller(ll p,ll iteration)
{
    if(p<2)
    {
        return false;
    }
    if(p!=2 && p%2==0)
    {
        return false;
    }
    ll s=p-1;
    while(s%2==0)
    {
        s/=2;
    }
    for(ll i=0; i<iteration; i++)
    {
        ll a=rand()%(p-1)+1,temp=s;
        ll mood=bigmod(a,temp,p);
        while(temp!=p-1 && mood!=1 && mood!=p-1)
        {
            mood=mulmod(mood,mood,p);
            temp *= 2;
        }
        if(mood!=p-1 && temp%2==0)
        {
            return false;
        }
    }
    return true;
}

/*********************************Extended_Euclid****************************/
ll Extended_Euclid(ll A, ll B, ll *X, ll *Y)///pointer take the address
{
    ll x, y, u, v, m, n, a, b, q, r;
    x = 0;
    y = 1;                ///* B = A(0) + B(1) */
    u = 1;
    v = 0;                ///* A = A(1) + B(0) */
    for (a = A, b = B; 0 != a; b = a, a = r, x = u, y = v, u = m, v = n)
    {
        q = b / a;        ///* b = aq + r and 0 <= r < a */
        r = b % a;
        m = x - (u * q);  ///* r = Ax + By - aq = Ax + By - (Au + Bv)q = A(x - uq) + B(y - vq) */
        n = y - (v * q);
    }
    *X = x;
    *Y = y;               ///* Ax + By = gcd(A, B) */
    return b;
}


/*********************************modInverse****************************/
ll modInverse(ll a, ll m)   ///a the number whose modular inverse will be counted
{
    ///m is the mod value
    ll m0 = m, t, q;
    ll x0 = 0, x1 = 1;
    if (m == 1) return 0;
    while (a > 1)
    {
        q = a / m;
        t = m;
        m = a % m, a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }
    if (x1 < 0)
        x1 += m0;
    return x1;
}


int main()
{
    ll i,j,t,k,l,m,n;
    cin>>t;
    while(t--)
    {
        cin>>m>>n;
        if(Fermat(m,n))
            cout<<"Yes\n";
        else
            cout<<"No\n";
        ll x,y;
        //k=Extended_Euclid(m,n,&x,&y);
     //   cout<<x<<"  "<<y<<"  "<<Extended_Euclid(m,n,&x,&y)<<endl;
    }
    return 0;
}