Ema 是游戏里最强的输出位。在游戏中，她需要消灭 $m$ 只怪物。第 $i$ 只怪物初始时有 $h_i$ 点生命值（HP）。当 Ema 攻击一只怪物时，它的 HP 会减少她的攻击力。当怪物的 HP 小于或等于 0 时，该怪物被消灭。

为了增加游戏的趣味性，攻击力不是一个常数。存在一个基础攻击序列 $a_1, a_2, \dots, a_n$，造成的伤害由该序列循环生成。形式化地，设 $r_i$ 为第 $i$ 次攻击造成的伤害，则有：

$$r_i = \begin{cases} a_i & 1 \le i \le n \\ r_{i-n} & i > n \end{cases}$$

为了尽快消灭怪物，Ema 希望最小化攻击次数。你能告诉她消灭所有怪物所需的最少攻击次数吗？

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示基础攻击序列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 3$)，表示基础攻击序列。 第三行包含一个整数 $m$ ($1 \le m \le 10^5$)，表示怪物的数量。 第四行包含 $m$ 个整数 $h_1, h_2, \dots, h_m$ ($1 \le h_i \le 10^9$)，其中 $h_i$ 表示第 $i$ 只怪物的初始 HP。

保证所有测试数据中 $n$ 的总和与 $m$ 的总和均不超过 $10^5$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示消灭所有怪物所需的最少攻击次数。

样例

输入格式 1

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

输出格式 1

4
3

说明

对于第一个样例，伤害序列为 $3, 2, 3, 2, 3, 2, \dots$。我们可以按顺序攻击怪物 1、2、3 和 2，从而消灭所有 3 只怪物。

对于第二个样例，我们可以按顺序攻击怪物 2、2、1。