Ada 正在为学校做一个科学项目。她正在研究进化，并希望比较不同物种在尝试解决编程竞赛问题时的表现。

物种编号为 $1$ 到 $N$（包含 $1$ 和 $N$）。物种 $1$ 没有直接祖先，其他所有物种都有且仅有一个直接祖先，它们是从该祖先直接进化而来的。物种 $x$ 的（不一定是直接的）祖先是指任何其他物种 $y$，使得从 $x$ 开始，通过一次或多次移动到物种的直接祖先，可以到达 $y$。这样，物种 $1$ 是所有其他物种的（直接或间接）祖先。

通过复杂的遗传模拟，她计算出了 $N$ 个物种中每个物种在特定编程竞赛中可能获得的平均分数。$S_i$ 是物种 $i$ 的平均分数。

Ada 正在寻找“有趣的”三元组以在她的演示文稿中展示。一个有趣的有序三元组 $(a, b, c)$ 由不同的物种组成，需满足：

1. 物种 $b$ 是物种 $a$ 的（直接或间接）祖先。
2. 物种 $b$ 不是物种 $c$ 的（直接或间接）祖先。
3. 物种 $b$ 的平均分数严格大于物种 $a$ 和物种 $c$ 分数的 $K$ 倍。即：$S_b \ge K \times \max(S_a, S_c) + 1$。

给定物种的分数和祖先关系，请编写一个程序来计算有趣的有序三元组的总数。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含两个整数 $N$ 和 $K$，分别表示物种的数量和确定有趣三元组的因子。 每个测试用例的第二行包含 $N$ 个整数 $S_1, S_2, \dots, S_N$，其中 $S_i$ 表示物种 $i$ 的平均分数。 每个测试用例的第三行包含 $N-1$ 个整数 $P_2, P_3, \dots, P_N$，表示物种 $P_i$ 是物种 $i$ 的直接祖先。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是根据 Ada 的定义计算出的有趣三元组的总数。

数据范围

$1 \le T \le 100$。 $1 \le K \le 10^9$。 $1 \le S_i \le 10^9$，对于所有 $i$。 $1 \le P_i \le N$，对于所有 $i$。 物种 $1$ 是所有其他物种的（直接或间接）祖先。

测试集 1（可见判定） $3 \le N \le 1000$。

测试集 2（隐藏判定） 对于最多 30 个用例： $3 \le N \le 2 \times 10^5$。 对于其余用例： $3 \le N \le 1000$。

样例

样例输入 1

2
5 2
3 3 6 2 2
3 1 1 3
7 3
2 4 7 2 2 1 8
6 1 7 3 1 3

样例输出 1

Case #1: 1
Case #2: 7

说明

在样例 1 中，只有一个可能的有趣三元组：$(5, 3, 4)$。我们可以验证： 1. 物种 $b = 3$ 是物种 $a = 5$ 的祖先。 2. 物种 $b = 3$ 不是物种 $c = 4$ 的祖先。 3. 物种 $b = 3$ 的分数比物种 $a = 5$ 和 $c = 4$ 的分数都高出 $K$ 倍以上：$S_3 = 6 \ge K \times \max(S_4, S_5) + 1 = 2 \times \max(2, 2) + 1 = 5$。

样例 1 的物种进化树

在样例 2 中，有七个有趣的有序三元组： $(4, 3, 1)$ $(4, 3, 6)$ $(4, 7, 1)$ $(4, 7, 5)$ $(4, 7, 6)$ $(5, 3, 1)$ * $(5, 3, 6)$

样例 2 的物种进化树