#include<bits/stdc++.h>

#define N 100005

#define M 10000005

#define lowbit(x) x&(-x)

#define LL long long

#define inf 0x3f3f3f3f

using namespace std;

inline int ra()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

map<int ,bool > mp;

int n,m,k,cnt;

LL p[N];

void getprime(LL x)

{

    for (LL i=; i*i<=x; i++)

    {

        if (x%i== && !mp[i])

        {

            mp[i]=; p[++cnt]=i;

        }

        while (x%i==) x/=i;

    }

    if (x> && !mp[x]) mp[x]=,p[++cnt]=x;

}

LL dfs(int pos, LL x)

{

    LL ans=;

    for (int i=pos; i<=cnt; i++)

        ans+=x/p[i]-dfs(i+,x/p[i]);

    return ans;

}

LL find(LL l, LL r, LL k)

{

    while (l<=r)

    {

        LL mid=l+r>>;

        if ((mid-dfs(,mid))<k) l=mid+;

        else r=mid-;

    }

    return l;

}

int main()

{

    int T=ra(); int cse=;

    while (T--)

    {

        n=ra(); m=ra(); k=ra();

        mp.clear(); cnt=;

        getprime((LL)n); getprime((LL)m);

        printf("Case %d: %I64d\n",++cse, find(1LL,1000000000000000LL,(LL)k));

    }

    return ;

}