罗马数字中有七个字符 IVXLCDM，分别表示 $1$，$5$，$10$，$50$，$100$，$500$，$1000$。

现在你将使用罗马数字与阿拉伯数字，在十进制下混合表示一个正整数，例如 $\texttt{X}2 = 10\times 10^1 + 2 \times 10^0=102$，$\texttt{IV}=1\times 10^1+5\times 10^0=15$。

对于每种数字，在表示中使用一次有一定的花费。求一个正整数使用用混合表示时的最小花费。

Input

第一行一个正整数 $T$（$1\le T\le 2\cdot 10^3$），表示数据组数。

对于每组数据，第一行一个正整数 $n$（$1\le n\le 10^{18}$），表示要表示的正整数。

第二行 10 个正整数 $c_0,c_1,\ldots,c_9$（$1\le c_i\le 10^7$），分别表示在混合表示中使用一次阿拉伯数字 $0$ 到 $9$ 的花费。

第三行 7 个正整数 $c_{\texttt{I}},c_{\texttt{V}},\ldots,c_{\texttt{M}}$（$1\le c_i\le 10^7$），分别表示在混合表示中使用一次罗马数字 I 到 M 的花费。

Output

对于每组数据输出一行一个整数，表示在混合使用罗马数字与阿拉伯数字的情况下，使用十进制表示这个正整数所需的最小花费。

5
102
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1
112
1 5 5 1 1 1 1 1 1 1
1 1 1 1 1 1 1
150
1 1 1 1 1 1 1 1 1 1
5 5 5 5 5 5 5
114514
10 5 5 1 1 1 1 1 1 1
1 1 1 1 1 1 1
1919810
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1

2
7
3
6
6

样例解释

$102$ 可以用 $\texttt{X}2$，$\texttt{I}02$ 和 $102$ 表示，其中花费最小的表示为 $\texttt{X}2$，所需花费为 $2$。

$112$ 可以用 $\texttt{I}12$，$1\texttt{I}2$，$\texttt{II}2$ 和 $112$ 表示，其中花费最小的表示为 $\texttt{II}2$，所需花费为 $7$。

$150$ 可以用 $\texttt{XL}$，$\texttt{5C}$，$10\texttt{L}$ 等表示，其中花费最小的表示为 $150$，所需花费为 $3$。