你是一个奸商，你甚至将金钱看得比你的性命还重要，所以你被巨人抓了起来。

巨人给了你一个字符串，字符串中只包含字母表中的前 $17$ 个字母，即 a ∼ q，并将会对所有长度 $\ge len$ 的子串进行检查，如果有任意一个子串不是优秀的，他就会处决你。

对于一个长度为 $n$ 的字符串 $s$，如果至少存在一个位置 $i \ (1 \le i \le n)$ 满足 $s[i] = s[n+1-i]$，就称此字符串是优秀的。

现在，你可以花费一定代价使巨人对某些字母产生幻视，例如，如果巨人对字母 d 产生幻视，那么在检查过程中，巨人可能会将字符 d 识别成某个 ASCII 码 $\ge$ d 且 $\le$ q 的字符，即 d, e, f, …, q。

请注意：

• 巨人会对字符串中所有的字符 d 产生幻视；
• 巨人在检查不同子串时，可能会对同一个字符 d 有不同的幻视。

例如，对于字符串 acde，假设巨人仅对字母 a 产生幻视：

• 检查不优秀的子串 acde 时，巨人可能识别成优秀的字符串 ecde；
• 检查不优秀的子串 ac 时，巨人可能识别成优秀的字符串 cc。

前文提到，你爱财如命，所以你希望在有生还希望的前提下，花费最小的代价，请你打印这个代价。

Input

第一行包含一个整数 $T$，表示测试数据的组数，$1 \le T \le 100$。

对于每组测试数据：

• 第一行包含一个整数 $n$，表示字符串的长度；
• 第二行给出一个长度为 $n$ 的字符串；
• 第三行包含 $17$ 个整数 $w_i \ (1 \le w_i \le 10^6)$，分别表示使巨人对字母 a ∼ q 产生幻视需要的代价；
• 第四行包含一个整数 $len \ (len \le n)$，巨人会对所有长度 $\ge len$ 的子串进行检查。

数据保证：$\sum n \le 3000$。

Output

请你打印在有生还希望的前提下，花费的最小代价。

Sample

Input

1
5
encle
1 1 8 3 4 4 8 4 2 4 6 8 9 8 2 2 8
2

Output

12