// Bobeş Bianca Maria
// C.N. "Andrei Şaguna"
// clasa a10a
// [email protected]
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int prim(int x)
{
    int d;
    if(x<2 || (x>2 && x%2==0))
        return 0;
    for(d=3; d*d<x; d+=2)
    {
        if(x%d==0)
            return 0;
    }
    return 1;

}
int nrdivp(int n)
{
    int d,cnt=0;
    if(n%2==0)
        cnt++;
    for(d=3; d<=n; d+=2)
    {
        if(n%d==0 && prim(d)==1)
            cnt++;
    }
    return cnt;
}
int main()
{
    int T,N,K;
    fin>>T;
    for(int i=1; i<=T*2; i++)
    {
        fin>>N>>K;
        for(int j=N; j>=0; j--)
        {
            if(nrdivp(N)==K)
            {
                fout<<j<<"\n";
                break;
            }
            if(j==0)
                fout<<0<<"\n";
                break;

        }

    }


    return 0;
}