#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
int a[10000],s=0;
for ( int i=2;i<=sqrt(n);i++){
while(n%i==0){
a[s]=i;
s++;
n=n/i;
}
}
if(n>1){
a[s]=n;
s++;
}
if(a[k-1]!=0) cout<<a[k-1]<<endl;
else cout<<"-1"<<endl;
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpewoJaW50IHQ7CgljaW4+PnQ7Cgl3aGlsZSh0LS0pewoJCWludCBuLGs7CgkJY2luPj5uPj5rOwoJCWludCBhWzEwMDAwXSxzPTA7CgkJZm9yICggaW50IGk9MjtpPD1zcXJ0KG4pO2krKyl7CgkJCXdoaWxlKG4laT09MCl7CgkJCQlhW3NdPWk7CgkJCQlzKys7CgkJCQluPW4vaTsKCQkJfSAKCQl9CgkJaWYobj4xKXsKCQkJYVtzXT1uOwoJCQlzKys7CgkJCQoJCX0gCgkJaWYoYVtrLTFdIT0wKSBjb3V0PDxhW2stMV08PGVuZGw7CgkJZWxzZSBjb3V0PDwiLTEiPDxlbmRsOwoJfQoJfQ==