#include<iostream>
#include<fstream>
using namespace std;

int main(){
	
	ifstream f("divprim.in");
	ofstream g("divprim.out");
	int t;
	f >> t;
	
	for(int i = 0; i < t; i++)
	{
		int n, k;
		cin >> n >> k;
		
		for(int j = 1; j < n; j++)
		{
			int cnt = 0;
			if(n % j == 0 && is_prim(j)) cnt++;
			if(cnt == k) {cout << j << endl; break;
			}
			if (cnt < k) cout << 0 << endl;
		}
	}
	f.close();
	g.close();
}