#include <fstream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;

#define N_MAX 1000001
#define K_MAX 8

//////////// GLOBALS ////////////
int m[N_MAX][K_MAX], ndp[N_MAX];

///////////// MAIN /////////////
int main() {
	ifstream fin("divprim.in");
	ofstream fout("divprim.out");

	int t, n, k, i, j;

	// Read
	fin >> t;


    // Precompute
    for(i = 2; i <= N_MAX; i++) { // Eratosthenes
        if(ndp[i] == 0) {
            ndp[i] = 1;
            for(j = i + i; j <= N_MAX; j += i)
                ndp[j]++;
        }
    }

    for(i = 1; i <= N_MAX; i++) {
        for(j = 0; j < K_MAX; j++)
            m[i][j] = m[i - 1][j];
        for(j = 0; j < K_MAX; j++)
            m[i][ndp[i]] = i;
    }


	// Compute
    while(t--) {
        fin >> n >> k;


        // Print
        fout << m[n][k] << "\n";
    }
}