#include <bits/stdc++.h>

using namespace std;

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

int v[1000000];
vector<int> a[8];

int main()
{
    a[0].push_back(1);
    for(int i = 2 ; i <= 1000000 ; i++)
    {
        if( v[i] == 0 )
        {
            for(int j = i + i ; j <= 1000000 ; j += i)
            {
                v[j]++;
            }
        }
        if(v[i] < 8)
            a[ v[i] ].push_back(i);
    }

    int n, x, k;
    fin >> n;
    while(n--)
    {
        fin >> x >> k;
        int ls = 0;
        int ld = a[k].size() - 1;
        int ans = 0;
        while(ls <= ld)
        {
            int mij = (ls + ld) / 2;
            if( a[k][mij] <= x )
            {
                ans = a[k][mij];
                ls = mij + 1;
            }
            else
            {
                ld = mij - 1;
            }
        }
        fout << ans << '\n';
    }


    return 0;
}