#include <fstream>
using namespace std;

const char INPUT_FILE_NAME[] = "divprim.in";
const char OUTPUT_FILE_NAME[] = "divprim.out";
const int N_MAX = 1000000;
const int K_MAX = 7;

int **creeazaMatrice(int n, int m){
	int **matrice = new int* [n];
	for(int i = 1; i < n; ++i){
		matrice[i] = new int[m];
	}
	for(int j = 1; j < m; ++j){
		matrice[1][j] = 0;
	}

	return matrice;
}

void stergeMatrice(int **matrice, int n, int m){
	for(int i = 1; i < n; ++i){
		delete matrice[i];
	}
	delete matrice;
}

void completeazaRand(int **matrice, int nr, int nr_div_primi){
	for(int j = 1; j < nr_div_primi; ++j){
		matrice[nr][j] = matrice[nr-1][j];
	}
	matrice[nr][nr_div_primi] = nr;
	for(int j = nr_div_primi+1; j <= K_MAX; ++j){
		matrice[nr][j] = matrice[nr-1][j];
	}
}

int **ciurEratosteneModificat(int n){
	int *nr_prime = new int[n+1];
	int **matrice = creeazaMatrice(n+1, K_MAX+1);

	for(int i = 2; i <= n; ++i){
		nr_prime[i] = 0;
	}

	for(int i = 2; i <= n; ++i){
		if(nr_prime[i] == 0){
			for(int j = i; j <= n; j += i){
				++nr_prime[j];
			}
		}
		completeazaRand(matrice, i, nr_prime[i]);
	}
	delete nr_prime;

	return matrice;
}

int main(int argc, char *argv[]){
	int nr_teste, n, k;
	int **matrice;
	
	matrice = ciurEratosteneModificat(N_MAX);

	ifstream fin(INPUT_FILE_NAME);
	ofstream fout(OUTPUT_FILE_NAME);
	fin >> nr_teste;
	for(int i = 1; i <= nr_teste; ++i){
		fin >> n >> k;
		fout << matrice[n][k] << "\n";
	}
	fin.close();
	fout.close();
	stergeMatrice(matrice, N_MAX+1, K_MAX+1);

	return 0;
}