#include <iostream>

#include <cstdio>

using namespace std;

FILE *f, *g;

char p[1000001];

char div1[1000001];

int prime[8][300000];

int col[8];

int n, k;

void ciur()
{
    int i, j;

    int n = 1000001;

    p[0] = p[1] = 1;

    div1[2] = 1;

    for(i = 4; i <= n; i += 2)
        p[i] = 1, div1[i] ++;

    for(i = 3; i * 2 <= n; i += 2)
        if(p[i] == 0)
            for(j = 2 ; j * i <= n; j ++)
                p[j * i] = 1, div1[j * i] ++;

    for(i = 3; i <= n; i += 2)
        if(p[i] == 0)
            div1[i] = 1;
}

void maxPrim()
{
    int i;

    for(i = 2; i <= 1000000; i ++)
    {
       // printf("%d\n", div1[i]);

        prime[div1[i]][++ col[div1[i]]] = i;
    }
}

int caut(int n, int k)
{
    int i = 0, pas = 1 << 18;

    while(pas)
    {
        if(i + pas <= col[k] &&  prime[k][i + pas] <= n)
            i += pas;

        pas /= 2;
    }

    return i;
}


int main()
{

    ciur();

    maxPrim();

    f = fopen("divprim.in", "r");

    g = fopen("divprim.out", "w");

    int t;

    fscanf(f, "%d", &t);

    for(int i = 1; i <= t; i ++)
    {
        fscanf(f, "%d%d", &n, &k);

        if(k == 0)
            fprintf(g, "1");

        else
        {
            /*int left, right, mid;

            left = 1;

            right = col[k];

            while(left <= right)
            {
                mid = left + (right - left) / 2;

                if(prime[k][mid] == n)
                {
                    left = mid;

                    break;
                }

                else
                    if(prime[k][mid] > n)
                        right = mid - 1;
                else
                    left = mid + 1;
            }*/

            int x = caut(n, k);

            fprintf(g, "%d", x /*<= n*/ ?  prime[k][x] : 0);
        }

        fprintf(g, "\n");
    }

    fclose(f);

    fclose(g);

    return 0;
}