题目描述

给定两个非负整数序列：

$$a_0,a_1,\ldots,a_{n-1}$$

和

$$b_0,b_1,\ldots,b_{m-1}.$$

请计算下面这段 C 语言程序执行结束后变量 ans 的值：

unsigned int ans = 0;

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        ans += gcd(a[i], b[j]) ^ i ^ j;
    }
}

其中：

• gcd(x, y) 表示整数 $x$ 和 $y$ 的最大公约数；
• 规定 $\gcd(0,x)=x$，特别地，$\gcd(0,0)=0$；
• ^ 表示按位异或运算；
• 数组下标从 $0$ 开始；
• unsigned int 按 32 位无符号整数处理，发生溢出时相当于对 $2^{32}$ 取模。

也就是说，需要计算：

$$\operatorname{ans} = \left( \sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \left(\gcd(a_i,b_j)\oplus i\oplus j\right) \right) \bmod 2^{32}.$$

这里的 $\oplus$ 表示按位异或，而不是普通加法。

输入格式

第一行输入一个正整数 $T$，表示测试数据的组数。

对于每组测试数据：

• 第一行输入两个正整数 $n,m$，分别表示两个序列的长度；
• 第二行输入 $n$ 个非负整数 $a_0,a_1,\ldots,a_{n-1}$；
• 第三行输入 $m$ 个非负整数 $b_0,b_1,\ldots,b_{m-1}$。

输出格式

对于每组测试数据，输出一行一个非负整数，表示对应的答案。

答案按照 32 位无符号整数计算，即最终结果对 $2^{32}$ 取模。

数据范围

$$1\le T\le 85,$$ $$1\le n,m\le 2000,$$ $$0\le a_i,b_i\le 10^6.$$

样例

3
3 2
5 9 6
3 4
2 2
8 9
0 6
1 1
9
6

6
22
3

样例说明

第一组数据的答案为：

$$\begin{aligned} \operatorname{ans} ={}&(\gcd(5,3)\oplus 0\oplus 0) +(\gcd(5,4)\oplus 0\oplus 1)\\ &+(\gcd(9,3)\oplus 1\oplus 0) +(\gcd(9,4)\oplus 1\oplus 1)\\ &+(\gcd(6,3)\oplus 2\oplus 0) +(\gcd(6,4)\oplus 2\oplus 1)\\ ={}&1+0+2+1+1+1\\ ={}&6. \end{aligned}$$