hdu 5019
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <list>
#include <cassert>
#include <complex>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define all(x) (x).begin(),(x).end()
//#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define TWO(x) (1<<(x))
#define TWOL(x) (1ll<<(x))
#define clr(a) memset(a,0,sizeof(a))
#define POSIN(x,y) (0<=(x)&&(x)<n&&0<=(y)&&(y)<m)
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long ll;
typedef long double LD;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<ll> VL;
typedef vector<PII> VPII;
typedef complex<double> CD;
const int inf=0x20202020;
const ll mod=;
const double eps=1e-; ll powmod(ll a,ll b) //return (a*b)%mod
{ll res=;a%=mod;for(;b;b>>=){if(b&)res=res*a%mod;a=a*a%mod;}return res;}
ll powmod(ll a,ll b,ll mod) //return (a*b)%mod
{ll res=;a%=mod;for(;b;b>>=){if(b&)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) //return gcd(a,b)
{ return b?gcd(b,a%b):a;}
// head namespace Factor {
const int N=;
ll C,fac[],n,mut,a[];
int T,cnt,i,l,prime[N],p[N],psize,_cnt;
ll _e[],_pr[];
vector<ll> d; inline ll mul(ll a,ll b,ll p) { //return (a*b)%p
if (p<=) return a*b%p;
else if (p<=1000000000000ll) return (((a*(b>>)%p)<<)+(a*(b&((<<)-))))%p;
else {
ll d=(ll)floor(a*(long double)b/p+0.5);
ll ret=(a*b-d*p)%p;
if (ret<) ret+=p;
return ret;
}
} void prime_table(){ //prime[1..tot]: prime[i]=ith prime
int i,j,tot,t1;
for (i=;i<=psize;i++) p[i]=i;
for (i=,tot=;i<=psize;i++){
if (p[i]==i) prime[++tot]=i;
for (j=;j<=tot && (t1=prime[j]*i)<=psize;j++){
p[t1]=prime[j];
if (i%prime[j]==) break;
}
}
} void init(int ps) { //initial
psize=ps;
prime_table();
} ll powl(ll a,ll n,ll p) { //return (a^n)%p
ll ans=;
for (;n;n>>=) {
if (n&) ans=mul(ans,a,p);
a=mul(a,a,p);
}
return ans;
} bool witness(ll a,ll n) {
int t=;
ll u=n-;
for (;~u&;u>>=) t++;
ll x=powl(a,u,n),_x=;
for (;t;t--) {
_x=mul(x,x,n);
if (_x== && x!= && x!=n-) return ;
x=_x;
}
return _x!=;
} bool miller(ll n) {
if (n<) return ;
if (n<=psize) return p[n]==n;
if (~n&) return ;
for (int j=;j<=;j++) if (witness(rand()%(n-)+,n)) return ;
return ;
} ll gcd(ll a,ll b) {
ll ret=;
while (a!=) {
if ((~a&) && (~b&)) ret<<=,a>>=,b>>=;
else if (~a&) a>>=; else if (~b&) b>>=;
else {
if (a<b) swap(a,b);
a-=b;
}
}
return ret*b;
} ll rho(ll n) {
for (;;) {
ll X=rand()%n,Y,Z,T=,*lY=a,*lX=lY;
int tmp=;
C=rand()%+;
X=mul(X,X,n)+C;*(lY++)=X;lX++;
Y=mul(X,X,n)+C;*(lY++)=Y;
for(;X!=Y;) {
ll t=X-Y+n;
Z=mul(T,t,n);
if(Z==) return gcd(T,n);
tmp--;
if (tmp==) {
tmp=;
Z=gcd(Z,n);
if (Z!= && Z!=n) return Z;
}
T=Z;
Y=*(lY++)=mul(Y,Y,n)+C;
Y=*(lY++)=mul(Y,Y,n)+C;
X=*(lX++);
}
}
} void _factor(ll n) {
for (int i=;i<cnt;i++) {
if (n%fac[i]==) n/=fac[i],fac[cnt++]=fac[i];}
if (n<=psize) {
for (;n!=;n/=p[n]) fac[cnt++]=p[n];
return;
}
if (miller(n)) fac[cnt++]=n;
else {
ll x=rho(n);
_factor(x);_factor(n/x);
}
} void dfs(ll x,int dep) {
if (dep==_cnt) d.push_back(x);
else {
dfs(x,dep+);
for (int i=;i<=_e[dep];i++) dfs(x*=_pr[dep],dep+);
}
} void norm() {
sort(fac,fac+cnt);
_cnt=;
rep(i,,cnt) if (i==||fac[i]!=fac[i-]) _pr[_cnt]=fac[i],_e[_cnt++]=;
else _e[_cnt-]++;
} vector<ll> getd() {
d.clear();
dfs(,);
return d;
} vector<ll> factor(ll n) { //return all factors of n cnt:the number of factors
cnt=;
_factor(n);
norm();
return getd();
} vector<PLL> factorG(ll n) {
cnt=;
_factor(n);
norm();
vector<PLL> d;
rep(i,,_cnt) d.push_back(make_pair(_pr[i],_e[i]));
return d;
} bool is_primitive(ll a,ll p) {
//assert(miller(p));
vector<PLL> D=factorG(p-);
rep(i,,SZ(D)) if (powmod(a,(p-)/D[i].first,p)==) return ;
return ;
}
} ll x,y,k;
int _;
int main() {
Factor::init();
for (scanf("%d",&_);_;_--) {
scanf("%I64d%I64d%I64d",&x,&y,&k);
vector<ll> c=Factor::factor(gcd(x,y)); //c:all factors of gcd(x,y)
sort(all(c)); // =all common factors of x and y
reverse(all(c));
if (SZ(c)<k) puts("-1"); else printf("%I64d\n",c[k-]);
}
}