#include<cstdio>
    #include<algorithm>
    #include<vector>
    using namespace std;
    #define MAX 1000001
    #define pb push_back
    int T ,N, v[MAX] , k ;
    vector<int> Q[10];

    void ciur();

    int main()
    {
        for(int i = 1 ; i <= 7 ;++i )Q[i].pb(0);
        freopen("divprim.in" , "r" , stdin );
        freopen("divprim.out" , "w" , stdout );
        scanf("%d" , &T );
        ciur();
        for(int i = 2 ; i < MAX ; ++i )
            if(!v[i])Q[1].pb(i);
            else
                if(v[i] < 8)Q[v[i]].pb(i);
        for(int i = 1 ; i <= T ; ++i )
        {
            scanf("%d%d" , &N , &k );
            int p = lower_bound(Q[k].begin() , Q[k].end() , N)-Q[k].begin();
            if(Q[k][p] != N)p--;
            printf("%d\n" , Q[k][p]);
        }
        return 0;
    }

    void ciur()
    {
        for(int i = 4 ; i < MAX ; i+=2)
            v[i] = 1;
        for(int i = 3 ; i < MAX ; i+=2 )
            if(!v[i])
                for(int j = i+i ; j < MAX ; j += i)
                    v[j]++;
    }