#include <bits/stdc++.h>

using namespace std;

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

int ciur[1000002],n,i,t,dd,nr,j,ok;

int main()
{
    f>>nr;
    for(i=2; i*i<=1000000; i++)
    {
        if(ciur[i]==0)
        {
            for(t=2*i; t<=1000000; t=t+i)
            {
                ciur[t]++;
            }
        }
    }
    for(j=1; j<=nr; j++)
    {
        f>>n>>dd;
        ok=0;
        for(i=n; i>=1; i--)
        {
            if(ciur[i]==dd)
            {
                g<<i<<endl;
                ok=1;
                break;
            }
        }
        if(ok==0)
            g<<0<<endl;
    }
    return 0;
}