Elephant 教授有一个序列 $a_1, a_2, \dots, a_n$。他使用该序列生成了一个具有 $n$ 个顶点的无向图 $G$，顶点编号为 $1, 2, \dots, n$。

对于每一个偶数长度的连续子序列 $a_l, a_{l+1}, \dots, a_{l+2k-1}$，如果对于所有的 $i = 1, 2, \dots, k$，都有 $a_{l+i-1} = a_{l+k+i-1}$ 成立，那么 Elephant 教授会在 $G$ 中添加 $k$ 条边，其中第 $i$ 条边的端点为编号 $(l + i - 1)$ 和 $(l + k + i - 1)$ 的顶点，权重为 $w_k$。

Elephant 教授想知道 $G$ 的最小生成森林的总权重。

输入格式

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

第一行包含一个整数 $n$ ($2 \le n \le 3 \times 10^5$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)。

第三行包含 $\lfloor \frac{n}{2} \rfloor$ 个整数 $w_1, w_2, \dots, w_{\lfloor \frac{n}{2} \rfloor}$ ($1 \le w_i \le 10^9$)。

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

输出格式

对于每组测试数据，输出一行一个整数，表示 $G$ 的最小生成森林的总权重。

样例

样例输入 1

1
8
2 2 5 6 2 5 6 2
5 1 4 4

样例输出 1

21