#include<fstream>
#include<algorithm>
using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");

int i,j,a[1000005][15],b[1000005],n,k,t;

int main()
{

    for(i=2; i<=1000000; ++i)
        if(!b[i])
        {
            for(b[i]=1,j=2*i; j<=1000000; j+=i)
                ++b[j];
        }



    cin>>t;

    while(t--)
        cin>>n>>k,cout<<a[n][k]<<'\n';

    return 0;
}