Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Integer Points

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputDLS and JLS are bored with a Math lesson. In order to entertain themselves, DLS took a sheet of paper and drew $$$n$$$ distinct lines, given by equations $$$y = x + p_i$$$ for some distinct $$$p_1, p_2, \ldots, p_n$$$.

Then JLS drew on the same paper sheet $$$m$$$ distinct lines given by equations $$$y = -x + q_i$$$ for some distinct $$$q_1, q_2, \ldots, q_m$$$.

DLS and JLS are interested in counting how many line pairs have integer intersection points, i.e. points with both coordinates that are integers. Unfortunately, the lesson will end up soon, so DLS and JLS are asking for your help.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$), the number of test cases in the input. Then follow the test case descriptions.

The first line of a test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of lines drawn by DLS.

The second line of a test case contains $$$n$$$ distinct integers $$$p_i$$$ ($$$0 \le p_i \le 10^9$$$) describing the lines drawn by DLS. The integer $$$p_i$$$ describes a line given by the equation $$$y = x + p_i$$$.

The third line of a test case contains an integer $$$m$$$ ($$$1 \le m \le 10^5$$$), the number of lines drawn by JLS.

The fourth line of a test case contains $$$m$$$ distinct integers $$$q_i$$$ ($$$0 \le q_i \le 10^9$$$) describing the lines drawn by JLS. The integer $$$q_i$$$ describes a line given by the equation $$$y = -x + q_i$$$.

The sum of the values of $$$n$$$ over all test cases in the input does not exceed $$$10^5$$$. Similarly, the sum of the values of $$$m$$$ over all test cases in the input does not exceed $$$10^5$$$.

In hacks it is allowed to use only one test case in the input, so $$$t=1$$$ should be satisfied.

Output

For each test case in the input print a single integer — the number of line pairs with integer intersection points.

Example

Input

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

Output

3 1 0

Note

The picture shows the lines from the first test case of the example. Black circles denote intersection points with integer coordinates.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/25/2020 20:18:17 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|