#include <iostream>
#include <fstream>

using namespace std;

int n, i, j, st, dr, mid, k, T;
bool ciur[1000005];
int prim[1000005], nr[8];
int tabel[8][1000005];

int main () {
    
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    
    for (i = 2; i <= 1000000; i++)
	{
        if (ciur[i] == 0)
        {
			nr[1]++;	tabel[1][nr[1]] = i;
            for (j = 2; j*i <= 1000000; j++)
			{
				prim[i*j]++;
				ciur[i*j] = 1;
			}
        }
		else
		{
			nr[prim[i]]++;	tabel[prim[i]][nr[prim[i]]] = i;
		}
	}
	
	fin >> T;
	bool gasit = 0;
	for (i = 1; i <= T; i++)
	{
		fin >> n >> k;
		
		gasit = 0;
		st = 1;		dr = 20;
		while (st <= dr && gasit == 0)
		{
			mid = st + (dr-st)/2;
			if (tabel[k][mid] == n)		gasit = 1;
			if (tabel[k][mid] > n)		dr = mid-1;
			if (tabel[k][mid] < n)		st = mid+1;
		}
		
		while (tabel[k][mid] > n)	mid--;
		
		if (k == 0)		fout << 1 << "\n";
		else if (n < tabel[k][1])	fout << 0 << "\n";
		else if (tabel[k][mid] < n && tabel[k][mid+1] <= n)	mid++;
		else fout << tabel[k][mid] << "\n";
	}
	
	/*
	 deci bun.
	 mi-am gasit idee.
	 facem sa avem o matrice de 8 linii. Pe linia i se afla numerele cu i divizori primi.
	 cum aflu numarul de divizori primi?
	 parcurg numerele prime cu ciurul lui eratosthene si adaug 1 la multiplii lor si retin intr-un vector acel numar.
	 asa ca numarul de pe pozitia i va spune cati div primi are numarul i.
	 apoi caut binar cel mai mare numar mai mic ca n.
	 */
}