#include <fstream>
#include <iostream>
using namespace std;

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

int ciur[1000005], divv[1000005];
int div1, div2, div3, div4, div5, div6, div7;
int a[8][400000];


int main()
{
    int t, i, j;
    ciur[2] = 1;
    for(i = 3; i <= 1000000; i += 2)
        ciur[i] = 1;
    for(i = 2; i <= 1000000; i += 2)
        divv[i]++;
    for(i = 3; i <= 1000000; i += 2)
        if(ciur[i] == 1)
            for(j = i; j <= 1000000; j = j + i)
            {
                if(j == i) divv[j]++;
                else
                {
                    ciur[j] = 0;
                    divv[j]++;
                }
            }
        //    for(i=1;i<=20;i++) cout<<divv[i]<<" ";
    for(i = 1; i <= 1000000; i++)
    {
        if(divv[i] == 1) div1++;
        if(divv[i] == 2) div2++;
        if(divv[i] == 3) div3++;
        if(divv[i] == 4) div4++;
        if(divv[i] == 5) div5++;
        if(divv[i] == 6) div6++;
        if(divv[i] == 7) div7++;
    }
   // fout << div1 << " " << div2 << " " << div3 << " " << div4 << " " << div5 << " " << div6 << " " << div7;
    div1 = div2 = div3 = div4 = div5 = div6 = div7 = 0;
    for(i = 1; i <= 1000000; i++)
    {
        if(divv[i] == 1)
        {
            a[1][++div1] = i;
        }
        if(divv[i] == 2)
        {
            a[2][++div2] = i;
        }
        if(divv[i] == 3)
        {
            a[3][++div3] = i;
        }
        if(divv[i] == 4)
        {
            a[4][++div4] = i;
        }
        if(divv[i] == 5)
        {
            a[5][++div5] = i;
        }
        if(divv[i] == 6)
        {
            a[6][++div6] = i;
        }
        if(divv[i] == 7)
        {
            a[7][++div7] = i;
        }
    }
    a[1][0] = div1;
    a[2][0] = div2;
    a[3][0] = div3;
    a[4][0] = div4;
    a[5][0] = div5;
    a[6][0] = div6;
    a[7][0] = div7;
    int mijl, st, dr, gasit, n, k;
    fin >> t;
    for(i = 1; i <= t; i++)
    {
        gasit = 0;
        fin >> n >> k;
        st = 1;
        dr = a[k][0];
        while(st <= dr)
        {
            mijl = (st + dr) / 2;
            if(a[k][mijl] == n)
            {
                fout << n<<"\n";
                gasit = 1;
                break;
            }
            else
                if(a[k][mijl] < n)
                    st = mijl + 1;
                else
                    dr = mijl - 1;
        }
        if(gasit == 0)
            { if(st==1) {fout<<0<<"\n";continue;}
                if(a[k][st] < n) fout << a[k][st]<<"\n";
            else fout << a[k][st - 1]<<"\n";
            }
    }

    return 0;
}