#include <iostream>
using namespace std;
bool isPrime(long int n) 
{ 
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 
    if (n%2 == 0 || n%3 == 0) return false; 
 
    for (int i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
 
    return true; 
} 
int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--)
	{
		long int n,k;
		cin>>n>>k;
		int i =1;
		if(k>=n)
		{
		   cout<<"1"<<"\n";	
		}
		else if(isPrime(n) || k==1)
		{
			cout<<n<<"\n";
		}
		else
		{
			i=n/k;
		while(k<(n/i))
		{
			i++;
			while(n%i!=0)
			{
				i++;
			}
		}
 
		cout<<i<<"\n";
	  }
	}
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwpib29sIGlzUHJpbWUobG9uZyBpbnQgbikgCnsgCiAgICBpZiAobiA8PSAxKSAgcmV0dXJuIGZhbHNlOyAKICAgIGlmIChuIDw9IDMpICByZXR1cm4gdHJ1ZTsgCiAgICBpZiAobiUyID09IDAgfHwgbiUzID09IDApIHJldHVybiBmYWxzZTsgCiAgCiAgICBmb3IgKGludCBpPTU7IGkqaTw9bjsgaT1pKzYpIAogICAgICAgIGlmIChuJWkgPT0gMCB8fCBuJShpKzIpID09IDApIAogICAgICAgICAgIHJldHVybiBmYWxzZTsgCiAgCiAgICByZXR1cm4gdHJ1ZTsgCn0gCmludCBtYWluKCkgewoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJaW50IHQ7CgljaW4+PnQ7Cgl3aGlsZSh0LS0pCgl7CgkJbG9uZyBpbnQgbixrOwoJCWNpbj4+bj4+azsKCQlpbnQgaSA9MTsKCQlpZihrPj1uKQoJCXsKCQkgICBjb3V0PDwiMSI8PCJcbiI7CQoJCX0KCQllbHNlIGlmKGlzUHJpbWUobikgfHwgaz09MSkKCQl7CgkJCWNvdXQ8PG48PCJcbiI7CgkJfQoJCWVsc2UKCQl7CgkJCWk9bi9rOwoJCXdoaWxlKGs8KG4vaSkpCgkJewoJCQlpKys7CgkJCXdoaWxlKG4laSE9MCkKCQkJewoJCQkJaSsrOwoJCQl9CgkJfQoKCQljb3V0PDxpPDwiXG4iOwoJICB9Cgl9CglyZXR1cm4gMDsKfQ==

NQo0NSA3CjggMQo2IDEwCjk5OTk5OTczMyA5OTk5OTk3MzIKOTk5OTk5NzMzIDk5OTk5OTczMwo=

5
45 7
8 1
6 10
999999733 999999732
999999733 999999733