DLS 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. [Image]

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
    n = int(input())
    r1 = list(map(int, input().split()))
    m = int(input())
    r2 = list(map(int, input().split()))
    o11 = sum(t % 2 for t in r1) # Counts odd number
    o12 = n - o11
    o21 = sum(t % 2 for t in r2) # Counts odd number
    o22 = m - o21
    print (o11 * o21 + o12 * o22)

T = int(input())
for i in range(T):
    N = int(input())
    ps = list(map(int, input().split()))
    M = int(input())
    qs = list(map(int, input().split()))

    peven = 0
    podd = 0
    for i in ps:
        if i % 2 == 0:
            peven += 1
        else:
            podd += 1

    qeven = 0
    qodd = 0
    for i in qs:
        if i % 2 == 0:
            qeven += 1
        else:
            qodd += 1

    print(qeven * peven + qodd * podd)


from bisect import bisect
from collections import defaultdict
# l = list(map(int,input().split()))
# map(int,input().split()))
from math import gcd,sqrt,ceil,inf
from collections import Counter
import sys
sys.setrecursionlimit(1000000)
from bisect import bisect
from collections import defaultdict
# l = list(map(int,input().split()))
# map(int,input().split()))
from math import gcd,sqrt,ceil,inf,factorial,log2
from collections import Counter
# import sys
# sys.setrecursionlimit(10**9)
#
#
# def update(i,z,bit):
#
#     # print(i)
#     while i<len(bit):
#         bit[i]+=z
#         i+=i&-i
#         # print(i)
# def query(i,bit):
#     sum = 0
#
#     while i>0:
#         sum+=bit[i]
#         i-=i&-i
#
#     return sum
#
#
# n,q = map(int,input().split())
#
# l = list(map(int,input().split()))
# bit = [0]*(n+1)
# for i in range(n):
#     update(i+1,l[i],bit)
# pref = [0]
# la = l.copy()
# la.reverse()
# for i in la:
#     pref.append(pref[-1]+i)
#
# bit2 = [0]*(n+1)
# for i in range(n):
#     update(i+1,la[i],bit2)
#
# for _ in range(q):
#     yo = list(map(int,input().split()))
#     if la[0] == 1:
#         a,b,c,d = yo
#         x,y = c,d
#         i = b
#         z1 = (query(y,bit) - query(x-1,bit))*(x-i)
#         x+=1
#         i = n-y
#         j = n-x
#         z2 = (query(j,bit2) - query(i-1,bit2))
#         print(z1-z2)
#     else:
#         a,b,c = yo
#         update(b,c,bit)
#         z1 = query(n,bit2) - query(b-1,bit2)
#         j = n-b
#         update(j,z1,bit2)



t = int(input())

for i in range(t):
    n = int(input())
    l1 = list(map(int,input().split()))
    m = int(input())
    l2 =  list(map(int,input().split()))
    count1 = 0
    for i in l2:
        if i%2 == 0:
            count1+=1
    count2 = m-count1
    ans = 0
    for i in l1:
        if i%2 == 0:
            ans+=count1
        else:
            ans+=count2
    print(ans)




def mi():
        return list(map(int, input().split()))
'''
3
3
1 3 2
2
0 3
1
1
1
1
1
2
1
1
'''
for _ in range(int(input())):
    n = int(input())
    a = list(mi())
    m = int(input())
    b = list(mi())

    oa,ob,ea,eb=0,0,0,0
    for i in a:
        if i%2:
            oa+=1
        else:
            ea+=1
    for i in b:
        if i%2:
            ob+=1
        else:
            eb+=1

    print(ea*eb+oa*ob)


for _ in range(int(input())):
    n = int(input())
    o1 = e1 = 0
    for i in list(map(int,input().split())):
        if i%2==1:
            o1+=1
    e1 = n-o1
    o2 = e2 = 0
    m = int(input())
    for i in list(map(int,input().split())):
        if i%2==1:
            o2+=1
    e2 = m-o2
    print(e1*e2 + o1*o2)

t = int(input())
for wefe in range(t):
	n = int(input())
	l = list(map(int,input().split()))
	m = int(input())
	k = list(map(int,input().split()))
	parl = 0
	park = 0
	for i in l:
		if i % 2 == 0:
			parl += 1
	for i in k:
		if i % 2 == 0:
			park += 1
	print(parl*park + (n-parl)*(m-park))

t=int(input())
for nt in range(t):
	n=int(input())
	ln=list(map(int,input().split()))
	m=int(input())
	lm=list(map(int,input().split()))
	lne,lno,lme,lmo=0,0,0,0
	for i in ln:
		if i%2==0:
			lne+=1
		else:
			lno+=1
	for i in lm:
		if i%2==0:
			lme+=1
		else:
			lmo+=1
	print (lne*lme+lno*lmo)	

t = int(input())
for _ in range(t):
    n = int(input())
    p = list(map(int, input().split()))
    m = int(input())
    q = list(map(int, input().split()))
    cnt_p0 = 0
    cnt_p1 = 0
    cnt_q0 = 0
    cnt_q1 = 0
    for i in range(n):
        if p[i] % 2 == 0:
            cnt_p0 += 1
        else:
            cnt_p1 += 1
    for i in range(m):
        if q[i] % 2 == 0:
            cnt_q0 += 1
        else:
            cnt_q1 += 1
    print(cnt_p0*cnt_q0 + cnt_p1*cnt_q1)

def get_cnt():
    n = int(input())
    a = list(map(int, input().split()))

    cnt = [0, 0]
    for x in a:
        cnt[x % 2] += 1

    return cnt

for _ in range(int(input())):
    p = get_cnt()
    q = get_cnt()

    ans = p[0] * q[0] + p[1] * q[1]
    print(ans)


import sys
import math
import itertools
import collections

def getdict(n):
    d = {}
    if type(n) is list or type(n) is str:
        for i in n:
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
    else:
        for i in range(n):
            t = ii()
            if t in d:
                d[t] += 1
            else:
                d[t] = 1
    return d
def divs(n, start=1):
    r = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if (n % i == 0):
            if (n / i == i):
                r.append(i)
            else:
                r.extend([i, n // i])
    return r
def cdiv(n, k): return n // k + (n % k != 0)
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(map(int, input().split()))
def lcm(a, b): return abs(a*b) // math.gcd(a, b)
def wr(arr): return '\n'.join(map(str, arr))
def revn(n): return int(str(n)[::-1])
def prime(n):
    if n == 2: return True
    if n % 2 == 0 or n <= 1: return False
    sqr = int(math.sqrt(n)) + 1
    for d in range(3, sqr, 2):
        if n % d == 0: return False
    return True


t = ii()
for i in range(t):
    n = ii()
    p = li()
    m = ii()
    q = li()
    po = pe = qo = qe = 0
    for i in range(n):
        if p[i] % 2 == 0:
            po += 1
        else:
            pe += 1
    for i in range(m):
        if q[i] % 2 == 0:
            qo += 1
        else:
            qe += 1
    print(qo * po + qe * pe)

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    m = int(input())
    b = list(map(int, input().split()))
    oa, ea, ob, eb = 0, 0, 0, 0
    for i in a:
        if i%2:
            oa+=1
        else:
            ea+=1
    for i in b:
        if i%2:
            ob+=1
        else:
            eb+=1
    print(oa*ob + ea*eb)

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); return
# template


def main():
    t = ii()
    for _ in range(t):
        n = ii()
        p = lmi()
        m = ii()
        q = lmi()
        op = 0
        oq = 0
        ep = 0
        eq = 0
        for x in p:
            if x % 2 == 0:
                ep += 1
            else:
                op += 1
        for x in q:
            if x % 2 == 0:
                eq += 1
            else:
                oq += 1
        print(op * oq + ep * eq)
    return


def __starting_point():
    main()

__starting_point()

t=int(input())
while t>0:
    t-=1
    n=int(input())
    a=[int(x) for x in input().split()]
    m=int(input())
    b=[int(x) for x in input().split()]
    e1=o1=e2=o2=0
    for i in a:
        if i%2==0:
            e1+=1
        else:
            o1+=1
    for i in b:
        if i%2==0:
            e2+=1
        else:
            o2+=1  
    s=e1*e2+o1*o2
    print(s)

import sys

t=int(sys.stdin.readline())

ans_arr=[]

for w in range(t):
	n=int(sys.stdin.readline())

	p=[int(i) for i in sys.stdin.readline().split()]

	m=int(sys.stdin.readline())

	q=[int(i) for i in sys.stdin.readline().split()]

	peven=0
	podd=0

	for e in range(n):
		if(p[e]%2==0):
			peven+=1
		else:
			podd+=1

	qeven=0
	qodd=0

	for f in range(m):
		if(q[f]%2==0):
			qeven+=1
		else:
			qodd+=1

	ans_arr.append(str(podd*qodd+peven*qeven))

print("\n".join(ans_arr))

t = int(input())
for _ in range(t):
    n = int(input())
    p = list(map(int, input().split()))
    m = int(input())
    q = list(map(int, input().split()))
    oddp = 0
    evenp = 0
    oddq = 0
    evenq = 0
    for i in range(n):
        if p[i] % 2 == 0:
            evenp += 1
        else:
            oddp += 1
    for i in range(m):
        if q[i] % 2 == 0:
            evenq += 1
        else:
            oddq += 1

    print(evenp*evenq + oddp*oddq)


t = int(input())
for test in range(t):
    n = int(input())
    a = list(map(int, input().split(" ")))
    m = int(input())
    b = list(map(int, input().split(" ")))
    odda = 0
    evena = 0
    oddb = 0
    evenb = 0
    res = 0
    for i in range(n):
        if a[i] % 2 == 0:
            evena+=1
        else:
            odda+=1
    for i in range(m):
        if b[i] % 2 == 0:
            evenb += 1
        else:
            oddb += 1
    res += (evena * evenb)
    res += (odda * oddb)
    print(res)

t = int(input())
ans = []
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    k = int(input())
    b = list(map(int, input().split()))

    f = [0,0]
    for el in a:
        f[el%2]+=1
    e = [0,0]
    for el in b:
        e[el%2]+=1
    ans.append(e[1]*f[1]+e[0]*f[0])

for el in ans:
    print(el)

t = int(input())
for _ in range(t):
    n = int(input())
    pis = list(map(int, input().split()))
    m = int(input())
    qis = list(map(int, input().split()))
    
    even = sum([1 if pi % 2 == 0 else 0 for pi in pis])
    odd = sum([1 if pi % 2 == 1 else 0 for pi in pis])
    ans = 0
    for qi in qis:
        if qi % 2 == 0:
            ans += even
        else:
            ans+=odd
    print(ans)


n=int(input())
for i in range(n):
    a=int(input())
    f=[int(x) for x in input().split()]
    b=int(input())
    g=[int(x) for x in input().split()]    
    odd1=0
    even1=0
    for h in range(a):
        if f[h] % 2 == 0:
            even1+=1
    odd1=a-even1
    odd2=0
    even2=0
    for h in range(b):
        if g[h] % 2 == 0:
            even2+=1
    odd2=b-even2
    print(odd2*odd1+even1*even2)


t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    m = int(input())
    b = list(map(int, input().split()))
    a1 = 0
    for x in a:
        if x % 2 == 0:
            a1 += 1
    b1 = 0
    for x in b:
        if x % 2 == 0:
            b1 += 1
    print(a1 * b1 + (len(a) - a1) * (len(b) - b1))


t = int(input())
for i in range(t):
    n = int(input())
    narr = list(map(int, input().split()))
    m = int(input())
    marr = list(map(int, input().split()))
    n0 = sum([1 for p in narr if p % 2 == 0])
    n1 = len(narr) - n0
    m0 = sum([1 for p in marr if p % 2 == 0])
    m1 = len(marr) - m0
    print(n0 * m0 + n1 * m1)