有一棵 $n$ 个结点的有根树 $T$。结点编号为 $1\dots n$，其中根结点为 $1$。

树上每条边的长度为 $1$。我们用 $d(x,y)$ 表示结点 $x,y$ 在树上的距离，$\text{LCA}(x,y)$ 表示 $x,y$ 的最近公共祖先（即树中最深的既是 $v$ 的祖先也是 $u$ 的祖先的结点）。

对于两个结点 $u,v$ $(u\ne v)$，令 $a=\text{LCA}(u,v)$，定义 $f(u,v)=gcd(d(u,a),d(v,a))$。其中 $gcd(x,y)$ 表示 $x,y$ 的最大公约数，特别地， $gcd(0,x)=gcd(x,0)=x$ $(x\ne 0)$。

对于所有 $i\in \{1,2,\cdots ,n-1\}$，求出有多少对 $(u,v)$ $(u<v)$，满足 $f(u,v)=i$。

输入格式

输入第一行包含一个正整数 $n$。保证 $n\ge 2$。

第 $2$ 到 $n$ 行中，第 $i$ 行有一个正整数 $p_i$，表示结点 $i$ 在树上的父亲是 $p_i$。保证 $p_i<i$。

输出格式

输出共 $n-1$ 行，其中第 $i$ 行表示对于 $i$ 的答案。

C/C++ 输入输出 long long 时请用 %lld。C++ 可以直接使用 cin/cout 输入输出。

样例一

input

5
1
2
2
1

output

8
2
0
0

样例二

input

8
1
2
3
4
1
6
6

output

16
9
2
1
0
0
0

样例三

见样例数据下载。

限制与约定

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载