罗马数字中有七个字符：I, V, X, L, C, D, M，分别代表 1, 5, 10, 50, 100, 500, 1000。

现在，你将使用罗马数字和阿拉伯数字来表示一个十进制的正整数。例如，$X2 = 10 \times 10^1 + 2 \times 10^0 = 102$，$IV = 1 \times 10^1 + 5 \times 10^0 = 15$。

对于每一位数字，其表示都有一定的代价。请找出使用混合表示法表示一个正整数的最小代价。

输入格式

第一行包含一个正整数 $T$ ($1 \le T \le 2 \cdot 10^3$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个正整数 $n$ ($1 \le n \le 10^{18}$)，表示要表示的整数。

第二行包含 10 个正整数 $c_0, c_1, \dots, c_9$ ($1 \le c_i \le 10^7$)，表示在混合表示法中使用阿拉伯数字 0 到 9 的代价。

第三行包含 7 个正整数 $c_I, c_V, \dots, c_M$ ($1 \le c_i \le 10^7$)，表示在混合表示法中使用罗马数字 I 到 M 的代价。

输出格式

对于每个测试用例，输出一个整数，表示使用罗马数字和阿拉伯数字的混合表示法来表示该十进制整数所需的最小代价。

样例

输入格式 1

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

输出格式 1

2
7
3
6
6

说明

102 可以表示为 X2, I02 和 102。代价最小的表示法是 X2，代价为 2。

112 可以表示为 I12, 1I2, II2 和 112。代价最小的表示法是 II2，代价为 7。

150 可以表示为 XL, 5C, 10L 等。代价最小的表示法是 150，代价为 3。