#include <iostream>

#include <cstdio>

using namespace std;

FILE *f, *g;

char p[1000001];

char div[1000001];

int prime[8][300000];

int col[8];

int n, k;

void ciur()
{
    int i, j;

    int n = 1000001;

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

    div[2] = 1;

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

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

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

void maxPrim()
{
    int i;

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

        prime[div[i]][++ col[div[i]]] = 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;
            }

            fprintf(g, "%d", prime[k][right]);
        }

        fprintf(g, "\n");
    }

    fclose(f);

    fclose(g);

    return 0;
}