Revenge of GCD

3
2 3 1
2 3 2
8 16 3

1
-1
2

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include<queue>
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

ll xx,yy,kk;

ll gcd(ll a,ll b)
{
    if(b==0)  return a;
    else  return gcd(b,a%b);
}

vector<ll>vec;

int main()
{
     ll i;
     int t;
     scanf("%d",&t);
     while(t--)
     {
        scanf("%I64d%I64d%I64d",&xx,&yy,&kk);
        ll  ans=gcd(xx,yy);
        vec.clear();
        vec.push_back(1);
        if(ans!=1)
            vec.push_back(ans);
        if(i*i==ans)
            vec.push_back(i);
        for(i=2;i*i<ans;i++)
          {
              if(ans%i==0)
              {
                  vec.push_back(i);
                  vec.push_back((ll)ans/i);
              }
          }
        sort(vec.begin(),vec.end());
       // printf("%d\n",vec.size());
        if(kk>vec.size())
              printf("-1\n");
        else
              printf("%I64d\n",vec[vec.size()-kk]);
    }
     return 0;
}