在他的漫长冒险中,史蒂夫偶然发现了一个村民村庄。村里的房子有双向小路相连。村里总共有$$$n$$$间房屋,编号从$$$1$$$到$$$n$$$。房屋和路径图表示一棵有根$$$^{\text{*}}$$$ 树$$$^{\text{†}}$$$,根位于市政厅所在的顶点$$$1$$$。
考虑任意房屋 $$$v$$$ 及其子树$$$^{\text{‡}}$$$。对于每个这样的房子 $$$v$$$ 和每个非负整数 $$$h$$$,考虑 $$$v$$$ 子树中与 $$$v$$$ 距离恰好 $$$h$$$ 的房子集合。这样的集合将被称为 公会。例如,对于 $$$h=0$$$,公会将仅由顶点 $$$v$$$ 组成。
在下面的示例中,显示了顶点 $$$v=4$$$ 的行会。 $$$h=0$$$ 的公会标记为红色,$$$h=1$$$ 的公会标记为浅蓝色,$$$h=2$$$ 的公会标记为绿色。
如果存在一个属于一个公会而不属于另一个公会的房屋,则两个公会被视为不同。史蒂夫想知道树中有多少个不同的非空公会。帮助他解决这个问题。
$$$^{\text{*}}$$$有根树是一棵树,其中一个顶点是特殊的,称为根。
$$$^{\text{†}}$$$树是没有环的连通图。
$$$^{\text{‡}}$$$顶点 $$$v$$$ 的子树是 $$$v$$$ 的子图、其所有后代以及它们之间的所有边。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 村庄中的房屋数量。
第二行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i \lt i$$$),其中 $$$p_i$$$ 是树中第 $$$i$$$ 房子的父代。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——村庄中不同行会的数量。
示例
输入复制
551 2 3 431 171 2 1 3 5 5101 1 3 2 2 4 4 4 3151 2 1 3 3 4 3 7 3 10 6 7 1 9
输出复制
5491522
注意
在第一个测试用例中,有 $$$5$$$ 公会,每个公会由一个房屋组成。
在第二个测试用例中,除了由单个房屋组成的行会之外,还有一个由顶点$$$2$$$和$$$3$$$组成的行会。它可以通过考虑顶点 $$$v=1$$$ 的子树中距离 $$$h=1$$$ 处的房屋来获得。
在第三个测试用例中,除了由单个房屋组成的行会之外,还有$$$2$$$行会:对于$$$v=1$$$和$$$h=1$$$,行会由顶点$$$2$$$和$$$4$$$组成;对于 $$$v=5$$$、$$$h=1$$$,公会由顶点 $$$6$$$ 和 $$$7$$$ 组成。