#include <iostream>
#include <fstream>

using namespace std;

int div(int n)
{
    int p = 0;
    int nr = 0;
    while(n % 2 == 0)
    {
        n /= 2;
        p ++;
    }
    if(p != 0)
        nr ++;

    for(int d = 3; d * d <= n; d += 2)
    {
        p = 0;
        while(n % d == 0)
        {
            n /= d;
            p ++;
        }
        if(p != 0)
            nr ++;
    }

    if(n > 1)
        nr ++;

    return nr;
}


int main()
{
    ifstream f ("divprim.in");
    ofstream g ("divprim.out");
    int t, n, k;
    f >> t;
    for(int i = 1; i <= t; i ++)
    {
        f >> n >> k;
        while(n)
        {
            if(div(n) == k)
            {
                g << n << endl;
                break;
            }
            n --;
        }

        if(n == 0)
            g << n << endl;

    }
    return 0;
}