Ryan_<

#include<bits/stdc++.h>
#define F(i,s,t) for(int i=(s);i<=(t);i++)
#define R(i,x) for(int i=head[x];i;i=e[i].nxt) 
using namespace std;
typedef long long LL;
LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int N=(int)1e5+10,M=(int)1e4;//每个数至多只有一个>sqrt(z)的质因子
int head[N],tot=0;
struct edge{int fro,go,nxt;LL w;}e[N<<1];
void addedge(int x,int y,LL z)
{
	e[++tot]=(edge){x,y,head[x],z};head[x]=tot;
	e[++tot]=(edge){y,x,head[y],z};head[y]=tot;
}
/*********************************************/
int d[N],pri[N];
LL C(int x)
{
	return x*100000000000000007LL+1234567890123567LL;
}
void gen_table()
{
	//d[1]=1;
	F(i,2,M){
		if(!d[i]) pri[++pri[0]]=i;
		F(j,1,pri[0]){
			int k=i*pri[j];
			if(k>M) break;
			d[k]=1;//当成bool数组使!
			if(i%k==0) break;
		}
	}
}
int n;LL ans;
map<LL,int> num;//!!!
void dfs(int x,int ff,LL v)
{
	ans+=num[v];//之前边权和为w的数的个数 
	num[v]++;
	R(i,x){
		int y=e[i].go;
		if(y==ff) continue;
		dfs(y,x,v^e[i].w);
	}
}
int main()
{
//	freopen(".in","r",stdin);
	gen_table();
	n=read();
	F(i,1,n-1){
		int x=read(),y=read();
		int z=read();LL w=0;//异或的初值赋为0 
		//将边权分解质因数: 
		F(j,1,pri[0]){
			int k=pri[j];
			if(k*k>z) break;//只需要枚举<=sqrt(z)的质数 
			bool t=0;//只需要bool型记录奇偶 
			while(z%k==0) t^=1,z/=k;
			if(t) w^=C(k);
		}
		if(z>1) w^=C(z);//每个数至多只有一个>sqrt(z)的质因子! 
		addedge(x,y,w);
	}
	dfs(1,0,0);
	printf("%lld\n",ans*2);
	return 0;
}