#include <iostream>
#include <fstream>
using namespace std;
int n,k,t,ok,d,p,x;
int promp(int x ,int div)
{
	int p=0,d=2;
	while(x!=1)
	if(x%d==0)
	{
		p++;
		if(p>d)
			return 0;
		while(x%d==0)
			x/=d;
	}
	d++;
	if(p==d)
		return 1;
	return 0;
}
int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    int a[2][n];
	for(int i=0;i<n;i++)
		f>>a[1][i]>>a[2][i];
	for(int i=0;i<n;i++)
	{
		int ok=1;
		while(ok && a[1][i]>0)
		{

			if (promp( a[1][i],a[2][i]==0))
				a[1][i]--;
		else
			ok=0;
	    }
		g<<a[1][i]<<"\n";
    }
	return 0;
}