#include<cstdio>
#include<iostream>
#include<algorithm>
#define M 200009
//#define N 100000
using namespace std;
struct data
{
int x,y,a1,yy;
}a[M];
struct dat
{
int F,id;
}b[M];
int n,mo[M],zhan[M],tnt,sum[M],st=,ans[M],N;
bool mark[M];
bool cmp(data b1,data b2)
{
return b1.a1<b2.a1;
}
bool cmp1(dat b1,dat b2)
{
return b1.F<b2.F;
}
void jia(int a1,int a2)
{
for(;a1<=N;a1+=a1&-a1)
sum[a1]+=a2;
return;
}
void mobiwus()
{
mo[]=;
for(int i=;i<=N;i++)
{
if(!mark[i])
{
zhan[++tnt]=i;
mo[i]=-;
}
for(int j=;i*zhan[j]<=N&&j<=tnt;j++)
{
mark[i*zhan[j]]=;
if(i%zhan[j])
mo[i*zhan[j]]=mo[i]*mo[zhan[j]];
else
mo[i*zhan[j]]=;
}
}
return;
}
int query(int a1)
{
int ss=;
for(;a1;a1-=a1&-a1)
ss+=sum[a1];
return ss;
}
void su(int n,int m,int j)
{
if(n>m)
swap(n,m);
int last=,re=;
for(int i=;i<=n;i=last+)
{
last=min(n/(n/i),m/(m/i));
re+=(n/i)*(m/i)*(query(last)-query(i-));
}
ans[j]=re;
return;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].a1);
a[i].yy=i;
N=max(N,a[i].x);
N=max(N,a[i].y);
}
sort(a+,a+n+,cmp);
mobiwus();
for(int i=;i<=N;i++)
{
b[i].F=;
b[i].id=i;
}
for(int i=;i<=N;i++)
for(int j=;j*i<=N;j++)
b[i*j].F+=i;
sort(b+,b+N+,cmp1);
for(int i=;i<=n;i++)
{
for(;b[st].F<=a[i].a1&&st<=N;st++)
for(int j=;j*b[st].id<=N;j++)
jia(j*b[st].id,b[st].F*mo[j]);
su(a[i].x,a[i].y,a[i].yy);
}
for(int i=;i<=n;i++)
printf("%d\n",ans[i]&0x7fffffff);
return ;
}
莫比乌斯反演