#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define _int64 long long

long long gcd(long long a,long long b){
    return b==0?a:gcd(b,a%b);
}

long long x,y,kk;

int main()
{
    int T=0;
    cin >> T;
    while (T--) {
        cin >> x >> y >> kk;
        long long d=gcd(x,y);
        vector<long long> ans;
        for (long long k=1;k*k<=d;++k) {
            if (d%k==0) {
                ans.push_back(k);
                if (k!=d/k)
                    ans.push_back(d/k);
            }
        }
        sort(ans.begin(),ans.end());
        reverse(ans.begin(),ans.end());
        if (kk>ans.size()) {
            cout << -1 << endl;
        } else {
            cout << ans[kk-1] << endl;
        }
    }
}