#include<cstdio>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef vector<int> VI;

 #define fi first

 #define se second

 #define MP make_pair

 #define N   110000

 #define M   41000

 #define eps 1e-8

 #define pi  acos(-1)

 #define oo  1e9

 int flag[N],prime[N],mu[N],t[N],ans[N],mx;

 struct node

 {

     int n,m,a,id;

 }q[N];

 pair<int,int> F[N];

 bool operator< (node a,node b)

 {

     return a.a<b.a;

 }

 int lowbit(int x)

 {

     return x&(-x);

 }

 void add(int x,int y)

 {

     while(x<=mx)

     {

         t[x]=t[x]+y;

         x+=lowbit(x);

     }

 }

 int query(int x)

 {

     int ans=;

     while(x)

     {

         ans+=t[x];

         x-=lowbit(x);

     }

     return ans;

 }

 void calc(int k)

 {

     int n=q[k].n;

     int m=q[k].m;

     int id=q[k].id;

     int i=;

     while(i<=n)

     {

         int x=n/i; int y=m/i;

         int t1=n/x; int t2=m/y;

         int pos=min(t1,t2);

         ans[id]+=x*y*(query(pos)-query(i-));

         i=pos+;

     }

 }

 int main()

 {

     freopen("bzoj3529.in","r",stdin);

     freopen("bzoj3529.out","w",stdout);

     int Q;

     scanf("%d",&Q);

     mx=;

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

     {

         scanf("%d%d%d",&q[i].n,&q[i].m,&q[i].a);

         q[i].id=i;

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

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

     }

     mu[]=;

     int tot=;

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

     {

         if(!flag[i])

         {

             prime[++tot]=i;

             mu[i]=-;

         }

         for(int j=;j<=tot;j++)

         {

             int t=prime[j]*i;

             if(t>mx) break;

             flag[t]=;

             if(i%prime[j]==)

             {

                 mu[t]=;

                 break;

             }

             mu[t]=-mu[i];

         }

     }

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

      for(int j=i;j<=mx;j+=i) F[j].fi+=i;

     for(int i=;i<=mx;i++) F[i].se=i;

     sort(q+,q+Q+);

     sort(F+,F+mx+);

     int j=;

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

     {

         while(j+<=mx&&F[j+].fi<=q[i].a)

         {

             j++;

             for(int k=F[j].se;k<=mx;k+=F[j].se)

              add(k,F[j].first*mu[k/F[j].se]);

         }

         calc(i);

     }

     for(int i=;i<=Q;i++) printf("%d\n",ans[i]&0x7fffffff);

     return ;

 }