#include<algorithm>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<iostream>

 #define ll long long

 #define inf 0x7fffffff

 std::pair<int,int>f[];

 struct node{

     int n,m,id,a;

 }q[];

 int mx,v[],p[],mark[],mul[],ans[];

 int lowbit(int x){

     return x&(-x);

 }

 int read(){

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

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

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

     return t*f;

 }

 int Read(){

     char ch=getchar();ll t=,f=;

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

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

     return t*f;

 }

 bool cmp(node a,node b){

     return a.a<b.a;

 }

 void add(int x,int y){

     for (int i=x;i<=mx;i+=lowbit(i)){

         v[i]+=y;

     }

 }

 int query(int x){

     int res=;

     if (x==) return ;

     for (int i=x;i;i-=lowbit(i)){

         res+=v[i];

     }

     return res;

 }

 void init(){

     mul[]=;

     for (int i=;i<=mx;i++){

         if (!mark[i]) {

             p[++p[]]=i;

             mul[i]=-;

         }

         for (int j=;j<=p[]&&i*p[j]<=mx;j++){

             mark[i*p[j]]=;

             if (i%p[j]) mul[i*p[j]]=mul[i]*(-);

             else {

                 mul[i*p[j]]=;

                 break;

             }

         }

     }

     for (int i=;i<=mx;i++)

      for (int j=i;j<=mx;j+=i)

       f[j].first+=i;

     for (int i=;i<=mx;i++) f[i].second=i;

 }

 void solve(int k){

     int id=q[k].id,n=q[k].n,m=q[k].m;

     for (int i=,j;i<=q[k].n;i=j+){

         j=std::min(n/(n/i),m/(m/i));

         ans[id]+=(n/i)*(m/i)*(query(j)-query(i-));

     }

 }

 int main(){

     int Q=read();

     for (int i=;i<=Q;i++){

         q[i].n=read(),q[i].m=read(),q[i].a=read();q[i].id=i;

         if (q[i].n>q[i].m) std::swap(q[i].n,q[i].m);

         mx=std::max(mx,q[i].n);

     }

     init();

     std::sort(q+,q++Q,cmp);

     std::sort(f+,f++mx);

     int now=;

     for (int i=;i<=Q;i++){

         while (now+<=mx&&f[now+].first<=q[i].a){

             now++;

             for (int j=f[now].second;j<=mx;j+=f[now].second){

                 add(j,f[now].first*mul[j/f[now].second]);

             }

         }

         solve(i);

     }

     for (int i=;i<=Q;i++)

      printf("%d\n",ans[i]&inf);

 }