/*input

*/
#include <bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define F(i,a,b) for(int i = a; i <= b; i++)
#define RF(i,a,b) for(int i = a; i >= b; i--)
#define pii pair<int,int>
#define PI 3.14159265358979323846264338327950288
#define ll long long
#define ff first
#define ss second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define debug(x) cout << #x << " = " << x << endl
#define INF 1000000009
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define P(x) printf("%d\n",x)
#define all(v) v.begin(),v.end()
#define MX 200005
ll a,k,n;
ll primes[5] = {2,3,5,7,11};
vector < ll > arr[5];
int main()
{
    std::ios::sync_with_stdio(false);
    ll temp = 1;
    F(i,0,63)
    {
        arr[0].pb(temp);
        temp = temp*2;
        if(temp <= 0)
            break;
    }
    temp = 1;
    F(i,0,39)
    {
        arr[1].pb(temp);
        temp = temp*3;
        if(temp <= 0)
            break;
    }
    temp = 1;
    F(i,0,27)
    {
        arr[2].pb(temp);
        temp = temp*5;
        if(temp <= 0)
            break;
    }
    temp = 1;
    F(i,0,22)
    {
        arr[3].pb(temp);
        temp = temp*7;
        if(temp <= 0)
            break;
    }
    temp = 1;
    F(i,0,18)
    {
        arr[4].pb(temp);
        temp = temp*11;
        if(temp <= 0)
            break;
    }
    F(i,0,63)
    {
        F(j,1,39)
        {
            if(i==0)
                continue;
            ll temp = (arr[0][i]) * (arr[1][j]);
            if(temp <= 0 || temp < arr[0][i] || temp<arr[1][j])
                break;
            arr[1].pb(temp);
        }
    }
    F(i,0,63)
    {
        F(j,0,39)
        {
            F(k,1,27)
            {
                if(i==0 && j==0)
                    continue;
                ll temp = (arr[0][i]) * (arr[1][j]) * (arr[2][k]);
                if(temp <= 0 || temp < arr[0][i] || temp<arr[1][j] || temp<arr[2][k])
                    break;
                arr[2].pb(temp);
            }
        }
    }
    F(i,0,63)
    {
        F(j,0,39)
        {
            F(k,0,27)
            {
                F(l,1,22)
                {
                    if(i==0 && j==0 && k==0)
                        continue;
                    temp = (arr[0][i]) * (arr[1][j]) * (arr[2][k]) * (arr[3][l]);
                    if(temp <= 0 || temp < arr[0][i] || temp<arr[1][j] || temp<arr[2][k] || temp < arr[3][l])
                        break;
                    arr[3].pb(temp);
                }
            }
        }
    }
    F(i,0,63)
    {
        F(j,0,39)
        {
            F(k,0,27)
            {
                F(l,0,22)
                {
                    F(m,1,18)
                    {
                        if(i==0 && j==0 && k==0 && l==0)
                            continue;
                        ll temp = (arr[0][i]) * (arr[1][j]) * (arr[2][k]) * (arr[3][l]) * (arr[4][m]);
                        if(temp <= 0 || temp < arr[0][i] || temp<arr[1][j] || temp<arr[2][k] || temp < arr[3][l] || temp < arr[4][m])
                            break;
                        arr[4].pb(temp);
                    }
                }
            }
        }
    }
    F(i,0,4)
        sort(arr[i].begin(),arr[i].end());
    /*F(i,0,62)
    {
        cout<<arr[0][i]<<endl;
    }*/
    ll t;
    cin>>t;
    while(t--)
    {
        ll ans;
        cin>>a>>k>>n;
        if(n==0)
        {
            cout<<a<<endl;
            continue;
        }
        else if(n==1)
        {
            vector <ll>::iterator it;
            ll id;
            F(i,0,4)
            {
                if(primes[i] == k)
                    id = i;
            }
            it = lower_bound(arr[id].begin(),arr[id].end(),a);
            if(*it == a)
            {
                it = it + n-1;
                ans = *it;
            }
            else
            {
                //debug(*it);
                it = it + n-1;
                ans = *it;
            }
            cout<<ans<<endl;
            continue;
        }
        vector <ll>::iterator it;
        ll id;
        F(i,0,4)
        {
            if(primes[i] == k)
                id = i;
        }
        it = lower_bound(arr[id].begin(),arr[id].end(),a);
        if(*it == a)
        {
            it = it + n-2;
            ans = *it;
        }
        else
        {
            //debug(*it);
            it = it + n-1;
            ans = *it;
        }
        cout<<ans<<endl;
    }
    return 0;
}