#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    ifstream cin ("divprim.in");
    ofstream cout ("divprim.out");

    int v[100000];
    int t, n, k, d=2, p=0, cj=0, cnt=0, found=0, cntv=0;
    cin >> t;
    for (int i=0; i<t; i++)
    {
        cin >> n >> k;
        found = 0;
        for (int j=n; j>0; j--)
        {
            cj = j;
            d = 2;
            cnt = 0;
            while(j > 1)
            {
                p = 0;
                while(j % d == 0)
                {
                    p++;
                    j /= d;
                }
                if(p)
                {
                    cnt++;
                    if (cnt > k)
                    {
                        break;
                    }
                }
                d++;
                if(j>1 && d * d > j)
                {
                    d = j;
                }
            }
            j = cj;
            if (cnt == k)
            {
                v[cntv] = j;
                cntv++;
                found = 1;
                break;
            }
        }
        if (found == 0)
        {
            v[cntv] = 0;
            cntv++;
        }
    }
    for (int i=0; i<t; i++)
    {
        cout << v[i] << endl;
    }
    return 0;
}