#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

typedef __int64 LL;
const int maxn=5*1e5+5;
int prime[maxn],mu[maxn],num,cnt[maxn],mbs[maxn][20];
bool flag[maxn];
void swap(int &a,int &b){ int t=a;a=b;b=t;}
int min(int a,int b){return a<b?a:b;}

void init()
{
    int i,j;
    mu[1]=1;cnt[1]=0;
    memset(flag,true,sizeof(flag));
    for(i=2;i<maxn;i++)
    {
        if(flag[i])
        {
            prime[num++]=i;mu[i]=-1;cnt[i]=1;
        }
        for(j=0;j<num&&i*prime[j]<maxn;j++)
        {
            flag[i*prime[j]]=false;
            cnt[i*prime[j]]=cnt[i]+1;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;break;
            }
            else mu[i*prime[j]]=-mu[i];
        }
    }
    memset(mbs,0,sizeof(mbs));
    for(i=1;i<maxn;i++)//求出单项的mbs[i][j]，表示的是i为公因子时的情况。
    for(j=i;j<maxn;j+=i)
        mbs[j][cnt[i]]+=mu[j/i];
    for(i=1;i<maxn;i++)  //以下是求前缀和
    for(j=0;j<19;j++)
        mbs[i][j]+=mbs[i-1][j];
    for(i=0;i<maxn;i++)
    for(j=1;j<19;j ++)
        mbs[i][j]+=mbs[i][j-1];
}

int main()
{
    num=0;
    init();
    int i,j,t,n,m,p;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d %d",&n,&m,&p);
        if(p>=19){ printf("%I64d\n",(LL)n*m);continue;}
        if(n>m) swap(n,m);
        LL ans=0;
        for(i=1,j=1;i<n;i=j+1)
        {
            j=min(n/(n/i),m/(m/i));
            ans+=(LL)(mbs[j][p]-mbs[i-1][p])*(n/i)*(m/i);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}