#include <iostream>

using namespace std;

int nr[1000003];

int main()
{
    int t, k = 0, n, i, j, l, nrdiv;
    int ciur[79000];
    for(i = 2; i < 1000000; i++){
        if(nr[i] == 0){
            for(j = 2; j <= 1000000 / i; j++)
                nr[j * i] = 1;
            ciur[k++] = i;
            }
        }
    cin>>t;
    for(i = 0; i < t; i++){
        cin>>n>>k;
        for(j = n; j > 1; j--){
            nrdiv = 0;
            for(l = 0; ciur[l] <= j && nrdiv <= k; l++){
                if(j % ciur[l] == 0)
                    nrdiv++;
                }
            if(nrdiv == k){
                cout<<j<<"\n";
                break;
                }
            }
        if(j == 1)
            cout<<0<<"\n";
        }
}