#include <iostream>
#include <fstream>

using namespace std;

int nr_fact_primi[100000];

int numar_factori_primi(int x)
{
    int nr=0;
    if(x%2==0)
    {
        nr++;
        while(x%2==0)
            x/=2;
    }
    for(int d=3; d<=x; d+=2)
    {
        if(x%d==0)
            nr++;
        while(x%d==0)
            x/=d;
    }
    return nr;
}

void genereaza_sir(int n)
{
    nr_fact_primi[0]=0,nr_fact_primi[1]=0;
    for(int i=2; i<n; i++)
    {
        nr_fact_primi[i]=numar_factori_primi(i);
    }
}


int rezolvare(int n, int k)
{
    if(k==0)
        return 1;
    for(int i=n; i>1; i--)
        if(nr_fact_primi[i]==k)
            return i;
    return 0;
}

int main()
{
    ifstream f ("divprim.in");
    ofstream g ("divprim.out");

    int t,n,k;
    f>>t;
    genereaza_sir(5000);
    for(int i=0; i<t; i++)
    {
        f>>n>>k;
        g<<rezolvare(n,k)<<endl;
    }
    return 0;
}


/*void ciur(int n)
{
    sir_ciur[1]=true;
    for(int i=2; i<=n/2; i++)
    {
        for(int j=2; i*j<=n; j++)
            sir_ciur[i*j]=true;
    }
}*/