#include <iostream>
#include <fstream>

using namespace std;

ifstream in("divprim.in");
ofstream out("divprim.out");

const int NMAX=1000000;
int v[NMAX+2];
int a[8][NMAX+2];

int gen(int n)
{
    int i;
    for(i=1; i<=n; i*=2)
    {
    }
    return i/2;
}

int caut(int x,int k,int n)
{
    int sol,step=gen(n);
    for(sol=1; step>0; step/=2)
    {
        if(sol+step<=n && a[k][sol+step]<=x)
            sol+=step;
    }
    return a[k][sol];
}

int main()
{
    int n,l=2;
    for(int i=2; i<=NMAX; i++)
    {
        if(v[i]==0)
        {
            for(int j=i+i; j<=NMAX; j+=i)
            {
                v[j]++;
            }
        }
    }
    in>>n;
    for(int i=1; i<=7; i++)
    {
        a[i][0]++;
    }
    for(int i=1; i<=NMAX; i++)
    {
            a[v[i]][a[v[i]][0]]=i;
            a[v[i]][0]++;
    }
    for(int i=1; i<=n; i++)
    {
        int x,k;
        in>>x>>k;
        int p = caut(x,k,a[k][0]-1);
        if(p>x)
            out<<0<<'\n';
        else
            out<<p<<'\n';
    }
    return 0;
}