//
//  main.cpp
//  divprim
//
//  Created by Andrada Minca on 24.12.2024.
//

#include <fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int t,n,k,v[10][1000005];
int divprim(int n,int k)
{
    int st=1,dr=v[k][0];
    while(st<dr)
    {
        int mij=(st+dr)/2;
        if(v[k][mij]<n)st=mij+1;
        else if(v[k][mij]>n)dr=mij;
        else return mij;
    }
    return st-1;
}
int main()
{
    fin>>t;
    v[1][0]=1;
    v[1][1]=2;
    for(int i=4;i<=1000000;i+=2)v[0][i]=1;
    for(int i=3;i<=1000000;i++)
    {
        if(!v[0][i])
        {
            for(long long h=i;h<=1000000;h+=i)v[0][h]++;
        }
        v[v[0][i]][0]++;
        v[v[0][i]][v[v[0][i]][0]]=i;
    }
    for(int i=1;i<=t;i++)
    {
        fin>>n>>k;
        fout<<v[k][divprim(n,k)]<<'\n';
    }
    return 0;
}