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

int t, k, n;
int vmax = 0;

int nr[100005];
int ku[100005];

int a[7][1000005];


int sirvmax(int n)
{
    for(int i=2; i<=n; i++)
        if(a[0][i] == 0)
        {
            for(int j=i; j<=n; j+=i)
                a[0][j]++;
        }
}


int form_mat()
{

    for(int i=1; i<=vmax; i++)
    {
        a[a[0][i]][++a[a[0][i]][0]] = i;
    }
}

int cautbin(int vm, int kk)
{
    int lg, i;
    for(lg = 1; lg<=vm; lg<<=1);
    for(i=0; lg!=0; lg>>=1)
        if(a[kk][i+lg] <= vm && i+lg <= a[kk][0])
            i+=lg;
    if(i == 0)
        return 0;
    return a[kk][i];

}


int main()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    scanf("%d", &t);
    for(int i=1; i<=t; i++)
    {
        scanf("%d %d", &nr[i], &ku[i]);
        if(nr[i] > vmax)
            vmax = nr[i];

    }
    sirvmax(vmax);
    form_mat();
    for(int i=1; i<=t; i++)
    {
        printf("%d\n", cautbin(nr[i], ku[i]));
    }


    return 0;

}