← 返回题目列表

Codeforces · 1248/A

A. 整数点

中文机器翻译题面 查看原题

DLS 和 JLS 对数学课感到厌倦。为了自娱自乐,DLS 拿了一张纸,画了 $$$n$$$ 不同的线,由方程 $$$y = x + p_i$$$ 给出一些不同的 $$$p_1, p_2, \ldots, p_n$$$。

然后 JLS 在同一张纸上画了 $$$m$$$ 不同的线,这些线由方程 $$$y = -x + q_i$$$ 给出,对于一些不同的 $$$q_1, q_2, \ldots, q_m$$$。

DLS 和 JLS 感兴趣的是计算有多少线对具有整数交点,即两个坐标均为整数的点。不幸的是,课程即将结束,因此 DLS 和 JLS 正在寻求您的帮助。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$),即输入中测试用例的数量。然后按照测试用例描述进行操作。

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$),即 DLS 绘制的行数。

测试用例的第二行包含 $$$n$$$ 不同的整数 $$$p_i$$$ ($$$0 \le p_i \le 10^9$$$) 描述 DLS 绘制的线条。整数 $$$p_i$$$ 描述了由方程 $$$y = x + p_i$$$ 给出的直线。

测试用例的第三行包含一个整数 $$$m$$$ ($$$1 \le m \le 10^5$$$),即 JLS 绘制的线数。

测试用例的第四行包含 $$$m$$$ 不同的整数 $$$q_i$$$ ($$$0 \le q_i \le 10^9$$$) 描述 JLS 绘制的线条。整数 $$$q_i$$$ 描述了由方程 $$$y = -x + q_i$$$ 给出的直线。

输入中所有测试用例的 $$$n$$$ 值的总和不超过 $$$10^5$$$。同样,输入中所有测试用例的 $$$m$$$ 值的总和不超过 $$$10^5$$$。

在 hacks 中,只允许在输入中使用一个测试用例,因此应该满足 $$$t=1$$$ 。

输出

对于输入中的每个测试用例,打印一个整数 - 具有整数交点的线对的数量。

示例

输入 #1

3
3
1 3 2
2
0 3
1
1
1
1
1
2
1
1

输出 #1

3
1
0

注意

该图显示了示例的第一个测试用例中的行。黑色圆圈表示与整数坐标的交点。