题目内容

在一个智能监测系统的数据处理中，工程师得到了三个长度均为 $n$ 的整数序列：传感器读数序列 $A$，基准序列 $B$ 以及一个下标映射序列 $K$。

现在需要统计所有满足 $1 \le i \le j \le n$ 且 $A_i = B_{K_j}$ 的有序对 $(i, j)$ 的个数。

请你编写程序，对给定的序列快速计算出结果。

数据范围

• 测试用例组数 $t$ 满足 $t \ge 1$，所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。
• 每组数据中序列长度 $n$ 满足 $1 \le n \le 10^5$。
• 序列 $A$ 和 $B$ 中的每个元素均为整数，且 $1 \le A_i, B_i \le 10^9$。
• 下标映射序列 $K$ 的每个元素 $K_j$ 均为整数，且 $1 \le K_j \le n$。

输入描述

第一行包含一个整数 $t$，表示测试用例组数。 接下来每组测试用例按以下格式给出： 第一行包含一个整数 $n$，表示当前用例的序列长度； 第二行包含 $n$ 个整数 $A_1, A_2, \dots, A_n$； 第三行包含 $n$ 个整数 $B_1, B_2, \dots, B_n$； 第四行包含 $n$ 个整数 $K_1, K_2, \dots, K_n$，含义如上所述。 数据保证满足上述范围约束。

输出描述

对于每组测试用例，输出一行一个整数，表示满足条件的有序对 $(i, j)$ 的数量。

样例1

输入

2
3
1 2 1
2 1 2
1 2 3
1
5
5
1

输出

2
1

说明

第一组数据：$n = 3$，$A = [1, 2, 1]$，$B = [2, 1, 2]$，$K = [1, 2, 3]$。

• 当 $j = 1$ 时，将 $A_1 = 1$ 加入前缀，$B_{K_1} = B_1 = 2$，前缀中 2 出现 0 次，累计答案 $0$。
• 当 $j = 2$ 时，将 $A_2 = 2$ 加入前缀，$B_{K_2} = B_2 = 1$，前缀中 1 出现 1 次，累计答案 $1$。
• 当 $j = 3$ 时，将 $A_3 = 1$ 加入前缀，$B_{K_3} = B_3 = 2$，前缀中 2 出现 1 次，累计答案 $2$。 满足条件的 $(i, j)$ 为 $(1,2)$ 和 $(2,3)$，总数为 2。

第二组数据：$n = 1$，$A = [5]$，$B = [5]$，$K = [1]$。当 $j = 1$ 时，将 $A_1 = 5$ 加入前缀，$B_{K_1} = B_1 = 5$，前缀中 5 出现 1 次，答案为 1。

样例2

输入

1
4
100 200 100 300
300 100 200 100
4 1 2 3

输出

4

说明

$n = 4$，$A = [100, 200, 100, 300]$，$B = [300, 100, 200, 100]$，$K = [4, 1, 2, 3]$。

• $j = 1$：$A_1 = 100$ 入前缀，查 $B_{K_1} = B_4 = 100$，前缀含 100 共 1 次，答案 $+1$。
• $j = 2$：$A_2 = 200$ 入前缀，查 $B_{K_2} = B_1 = 300$，前缀无 300，答案 $+0$。
• $j = 3$：$A_3 = 100$ 入前缀，查 $B_{K_3} = B_2 = 100$，前缀含 100 共 2 次，答案 $+2$。
• $j = 4$：$A_4 = 300$ 入前缀，查 $B_{K_4} = B_3 = 200$，前缀含 200 共 1 次，答案 $+1$。 最终答案为 1+0+2+1=4，对应有序对 $(1,1)$、$(1,3)$、$(3,3)$、$(2,4)$。