#include <bits/stdc++.h>

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");

const int NMAX = 1e6 + 10;
const int LMAX = 8;
int n,k,T;
int ciur[NMAX];
int dp[NMAX][LMAX];

int main(){
    int i,j,x;

    for(int i = 2 ; i < NMAX ; i += 2)
        ciur[i] = 1;

    for(i = 3 ; i < NMAX ; i++)
        if(!ciur[i]){
            ciur[i] = 1;
            for(j = 2 * i ; j < NMAX ; j += i)
                ciur[j]++;
        }

    for(i = 1 ; i < NMAX ; i++)
        for(j = 0 ; j < LMAX ; j++){
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            dp[i][ciur[i]] = max(dp[i][ciur[i]], i);
        }

    f >> T;

    while(T--){
        f >> n >> k;
        g << dp[n][k] << "\n";
    }

    return 0;
}