#include <fstream>

using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
int ciur[1000005];
int dp[1000005][8];
int main()
{
    int t, i, j, div, test, n, k;


    for(i = 2; i <= 1000000; i ++)
    {
        if(!ciur[i])
            for(j = i; j <= 1000000; j += i)
            {
                ciur[j]++;
                if(ciur[j] <= 7)
                {
                    dp[j][ciur[j]] = j;
                    dp[j][ciur[j] - 1] = 0;
                }
                else
                    dp[j][7] = 0;
            }
    }



    for(div = 1; div <= 7; div ++)
    {
        for(j = 2; j <= 1000000; j++)
        {
            if(!dp[j][div])
                dp[j][div] = dp[j - 1][div];
        }
    }
    cin >> t;
    for(test = 1; test <= t; test++)
    {
        cin >> n >> k;
        if(k == 0)
            cout << 1;
        else
            cout << dp[n][k] << '\n';
    }


    return 0;
}