题目描述

PAREO 和 CHU \(^2\) 是一对关系很好的主仆，这天， CHU \(^2\) 有一道非常难的数学题不会做，因此她让 PAREO 把问题交给了你。

有两个长度分别为 \(n, m\) 的数组 \(a, b\)，求 \(\sum_{i = 1}^{n} \sum_{j = 1}^{m} \frac{lcm(a_i, b_j)}{gcd(a_i, b_j)}\)。

其中 \(gcd(x, y), lcm(x, y)\) 分别是求 \(x\) 和 \(y\) 的最大公约数、最小公倍数。由于最后的答案可能很大，因此你需要输出答案对 \(10^9 + 7\) 取模后的结果。

输入格式

第一行输入一个整数 \(T(1 \le T \le 5)\) 表示数据组数。

对于每组数据：

第一行输入两个正整数 \(n, m(1 \le n, m \le 10^6)\)，表示两个数组长度。

第二行输入 \(n\) 个正整数 \(a_i(1 \le a_i \le 10^6)\) 表示数组 \(a\)。

第三行输入 \(m\) 个正整数 \(b_i(1 \le b_i \le 10^6)\) 表示数组 \(b\)。

数据保证 \(\sum n \le 5 \times 10^6, \sum m \le 5 \times 10^6\)。

由于输入的数据量非常大，建议使用较快的输入方式，如在 C++ 中关闭同步流。

输出格式

对于每组数据输出一个整数表示答案对 \(10^9 + 7\) 取模后的结果。

样例输入

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

样例输出

15
45

提示

对于第一组样例：

lcm(1, 1) / gcd(1, 1) = 1 / 1 = 1

lcm(1, 4) / gcd(1, 4) = 4 / 1 = 4

lcm(1, 5) / gcd(1, 5) = 5 / 1 = 5

lcm(1, 1) / gcd(1, 1) = 1 / 1 = 1

lcm(1, 4) / gcd(1, 4) = 4 / 1 = 4

1 + 4 + 5 + 1 + 4 = 15