BaoBao 在森林里采蘑菇。森林里有 $n$ 个地点，第 $i$ 个地点生长着无穷多种类为 $t_i$ 的蘑菇。每个地点还有一个木牌，第 $i$ 个地点的木牌指向地点 $a_i$（可能存在 $a_i = i$）。

由于森林里雾很大，为了安全起见，BaoBao 决定按照木牌的指示在地点之间移动。从地点 $s$ 出发，篮子初始为空，每次 BaoBao 走进一个地点 $c$（包括起始地点 $c = s$，且无论他之前是否访问过地点 $c$），他都会将一个种类为 $t_c$ 的蘑菇放入篮子，并移动到地点 $a_c$。

给定一个整数 $k$，对于每个 $1 \le s \le n$，确定篮子中第一个出现次数达到至少 $k$ 次的蘑菇种类。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试数据组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 2 \times 10^5, 1 \le k \le 10^9$)，分别表示地点数量和蘑菇所需出现的次数。

第二行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$ ($1 \le t_i \le n$)，其中 $t_i$ 是生长在地点 $i$ 的蘑菇种类。

第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)，其中 $a_i$ 是地点 $i$ 的木牌所指向的地点。

保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

为了减小输出规模，对于每组测试数据，输出一行，包含一个整数，表示 $\sum_{i=1}^{n} (i \times v_i)$，其中 $v_i$ 是 $s = i$ 时的答案。

样例

样例输入 1

3
5 3
2 2 1 3 3
2 5 1 2 4
5 4
2 2 1 3 3
2 5 1 2 4
3 10
1 2 3
1 3 2

样例输出 1

41
45
14

说明

对于第一组样例，当 $v_1 = 2, v_2 = 3, v_3 = 2, v_4 = 3, v_5 = 3$ 时，你应该输出 $1 \times 2 + 2 \times 3 + 3 \times 2 + 4 \times 3 + 5 \times 3 = 41$。考虑 $s = 3$，BaoBao 按顺序采摘的蘑菇种类为 $\{1, 2, 2, 3, 3, 2, \dots \}$，因此种类为 2 的蘑菇是第一个在篮子中出现至少 3 次的种类。