DreamGrid 有 $n$ 个整数 $a_1, a_2, \dots, a_n$。DreamGrid 还有 $m$ 次查询，每次他都想知道对于给定的数 $p$，下式的值：

$$\sum_{1 \le i \le n} \left\lfloor \frac{a_i}{\lceil \log_p a_i \rceil} \right\rfloor$$

其中 $\lfloor x \rfloor = \max\{y \in \mathbb{Z} \mid y \le x\}$，$\lceil x \rceil = \min\{y \in \mathbb{Z} \mid y \ge x\}$。

输入格式

输入包含多组测试数据。第一行是一个整数 $T$，表示测试数据的组数。 对于每组测试数据： 第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 5 \times 10^5$)，分别表示整数的个数和查询的次数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 10^9$)。 第三行包含 $m$ 个整数 $p_1, p_2, \dots, p_m$ ($2 \le p_i \le 10^9$)。 保证所有 $n$ 之和与所有 $m$ 之和均不超过 $2 \times 10^6$。

输出格式

对于每组测试数据，输出一个整数 $(\sum_{i=1}^m i \cdot z_i) \pmod{10^9}$，其中 $z_i$ 是第 $i$ 次查询的答案。

样例

输入 1

2
3 2
100 1000 10000
100 10
4 5
2323 223 12312 3
1232 324 2 3 5

输出 1

11366
45619