STRNO

#define ll long long
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
    ll x,k;
    cin>>x>>k;
    int count=0;
    for(int i=2;i<=sqrt(x);i++)
    {
        while(x%i==0)
        {
            x=x/i;
            count++;
        }


    }
    if(x>2)
        count++;
    if(count>=k)
    {
        cout<<"1"<<endl;
    }
    else
        cout<<"0"<<endl;
    }

    return 0;
}