You are given an array A of length N. Find the number of pairs of indices (i,j) such that
1 ≤ i < j ≤ N
A_{i} \cdot A_{j} > 0

------ Input Format ------ 

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N - the size of the array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

------ Output Format ------ 

For each test case, output the number of pairs which satisfy the above conditions.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$-10^{4} ≤ A_{i} ≤ 10^{4}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
3
5
1 -3 0 2 -1
4
-1 -1 -1 -1
4
0 1 2 3

----- Sample Output 1 ------ 
2
6
3

----- explanation 1 ------ 
Test case 1: The pairs which satisfy the conditions are $(1,4)$ and $(2,5)$.

Test case 2: The pairs which satisfy the conditions are $(1,2)$, $(1,3)$, $(1,4)$, $(2,3)$, $(2,4)$ and $(3,4)$.

Test case 3: The pairs which satisfy the conditions are $(2,3)$, $(2,4)$ and $(3,4)$.

Source: codechef | Difficulty: EASY
Tags: Mathematics


Solutions:
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	n1 = len([x for x in a if x < 0])
	n2 = len([x for x in a if x > 0])
	print(n1 * (n1 - 1) // 2 + n2 * (n2 - 1) // 2)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = []
	c = []
	for i in range(n):
		if a[i] > 0:
			b.append(a[i])
		elif a[i] < 0:
			c.append(a[i])
		else:
			continue
	q = len(b)
	w = len(c)
	num = int(q * (q - 1) / 2 + w * (w - 1) / 2)
	print(num)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	lt = len([x for x in a if x < 0])
	gt = len([x for x in a if x > 0])
	print(lt * (lt - 1) // 2 + gt * (gt - 1) // 2)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(p, o) = (-1, -1)
	for i in range(n):
		if a[i] > 0:
			p += 1
		elif a[i] < 0:
			o += 1
	print(p * (p + 1) // 2 + o * (o + 1) // 2)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	p = []
	n = []
	z = []
	for i in A:
		if i > 0:
			p.append(i)
		elif i == 0:
			z.append(i)
		else:
			n.append(i)
	l1 = len(p)
	l2 = len(n)
	a = l1 * (l1 - 1) // 2
	b = l2 * (l2 - 1) // 2
	print(a + b)


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	(p, ne, ansp, ansne) = (0, 0, 0, 0)
	for i in li:
		if i > 0:
			p += 1
		elif i < 0:
			ne += 1
	if p > 1:
		for pi in range(1, p):
			ansp = ansp + pi
	if ne > 1:
		for nei in range(1, ne):
			ansne = ansne + nei
	print(ansne + ansp)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = list(filter(0 .__ne__, a))
	(p, ne) = (0, 0)
	for i in range(len(a)):
		if a[i] > 0:
			p += 1
		else:
			ne += 1
	print(p * (p - 1) // 2 + ne * (ne - 1) // 2)


t = int(input())
for tc in range(t):
	x = int(input())
	a = list(map(int, input().split()))
	p = []
	z = []
	n = []
	for j in range(x):
		if a[j] > 0:
			p.append(a[j])
		elif a[j] < 0:
			n.append(a[j])
		else:
			z.append(a[j])
	lp = len(p)
	ln = len(n)
	x = lp * (lp - 1)
	y = ln * (ln - 1)
	print(x // 2 + y // 2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	pos = []
	neg = []
	zero = []
	for i in a:
		if i > 0:
			pos.append(i)
		elif i == 0:
			zero.append(i)
		else:
			neg.append(i)
	l1 = len(pos)
	l2 = len(neg)
	x = l1 * (l1 - 1) // 2
	y = l2 * (l2 - 1) // 2
	print(x + y)


t = int(input())
while t:
	t = t - 1
	n = int(input())
	l = list(map(int, input().split()))
	z = 0
	x = 0
	for i in l:
		if i > 0:
			x = x + 1
		if i == 0:
			z = z + 1
	y = len(l) - z - x
	x = x * (x - 1) // 2 + y * (y - 1) // 2
	print(x)


for _ in range(int(input())):
	c = count = 0
	a = int(input())
	l = list(map(int, input().split()))
	for j in range(a):
		if l[j] > 0:
			count = count + 1
		elif l[j] < 0:
			c = c + 1
	print(count * (count - 1) // 2 + c * (c - 1) // 2)


t = int(input())
while t != 0:
	n = int(input())
	a = list(map(int, input().split(' ')))
	(p, neg, c) = (0, 0, 0)
	for i in a:
		if i > 0:
			p += 1
		elif i < 0:
			neg += 1
	if p > 0:
		c = p * (p - 1) // 2
	if neg > 0:
		c += neg * (neg - 1) // 2
	print(c)
	t -= 1


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	nc = 0
	pc = 0
	res = 0
	for i in arr:
		if i < 0:
			nc += 1
		elif i > 0:
			pc += 1
	if pc > 0:
		res = pc * (pc - 1) // 2
	if nc > 0:
		res += nc * (nc - 1) // 2
	print(res)


T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	(c1, c2) = (-1, -1)
	val = 0
	for i in A:
		if i > 0:
			c1 += 1
		elif i < 0:
			c2 += 1
	for i in A:
		if i > 0:
			val += c1
			c1 -= 1
		elif i < 0:
			val += c2
			c2 -= 1
	print(val)


for _ in range(int(input())):
	d = {'p': 0, 'n': 0}
	n = int(input())
	a = [int(x) for x in input().split()]
	for i in a:
		if i > 0:
			d['p'] += 1
		elif i < 0:
			d['n'] += 1
	print(d['p'] * (d['p'] - 1) // 2 + d['n'] * (d['n'] - 1) // 2)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(c1, c2) = (-1, -1)
	val = 0
	for x in l:
		if x > 0:
			c1 += 1
		elif x < 0:
			c2 += 1
	for x in l:
		if x > 0:
			val += c1
			c1 = c1 - 1
		elif x < 0:
			val += c2
			c2 = c2 - 1
	print(val)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	c1 = 0
	c2 = 0
	for e in a:
		if e > 0:
			c1 += 1
		if e < 0:
			c2 += 1
	ans = c1 * (c1 - 1) // 2 + c2 * (c2 - 1) // 2
	print(ans)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	(pos, neg) = [0] * 2
	for a in A:
		if a > 0:
			pos += 1
		elif a < 0:
			neg += 1
	print(pos * (pos - 1) // 2 + neg * (neg - 1) // 2)


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	(t, u) = (0, 0)
	for i in l:
		if i < 0:
			t += 1
		elif i > 0:
			u += 1
	print(int(t * (t - 1) / 2) + int(u * (u - 1) / 2))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	c1 = 0
	for j in l:
		if j > 0:
			c += 1
		elif j < 0:
			c1 += 1
	c2 = 0
	for j in range(1, c1):
		c2 += j
	for j in range(1, c):
		c2 += j
	print(c2)


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	(a, b) = (0, 0)
	for i in arr:
		if i > 0:
			a += 1
		elif i < 0:
			b += 1
	print(a * (a - 1) // 2 + b * (b - 1) // 2)
	t -= 1


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	negative = 0
	positive = 0
	for i in range(n):
		if a[i] < 0:
			negative += 1
		elif a[i] > 0:
			positive += 1
	print((positive ** 2 + negative ** 2 - positive - negative) // 2)


for _ in range(int(input())):
	z = int(input())
	l = list(map(int, input().split()))
	l1 = []
	l2 = []
	for i in l:
		if i > 0:
			l1.append(i)
		elif i < 0:
			l2.append(i)
	x = len(l1) * (len(l1) - 1) // 2 + len(l2) * (len(l2) - 1) // 2
	print(x)


import math
for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	neg = sum((i < 0 for i in a))
	pos = sum((i > 0 for i in a))
	print(math.comb(neg, 2) + math.comb(pos, 2))


for t in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	c1 = 0
	c2 = 0
	for i in m:
		if i > 0:
			c1 += 1
		if i < 0:
			c2 += 1
	print(c1 * (c1 - 1) // 2 + c2 * (c2 - 1) // 2)


for t in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	c1 = 0
	c2 = 0
	fact = 1
	fact1 = 1
	temp = 1
	temp1 = 1
	for i in m:
		if i > 0:
			c1 += 1
		if i < 0:
			c2 += 1
	for i in range(1, c1 + 1):
		fact = fact * i
		if i == c1 - 2:
			temp = fact
	for i in range(1, c2 + 1):
		fact1 = fact1 * i
		if i == c2 - 2:
			temp1 = fact1
	sum = fact // (temp * 2) + fact1 // (temp1 * 2)
	print(sum)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(pcount, ncount) = (0, 0)
	for i in l:
		if i >= 1:
			ncount += 1
		elif i < 0:
			pcount += 1
	print(ncount * (ncount - 1) // 2 + pcount * (pcount - 1) // 2)


for _ in range(int(input())):
	nm = int(input())
	lt = list(map(int, input().split()))
	ct = 0
	cnt = 0
	for i in lt:
		if i > 0:
			ct += 1
		elif i < 0:
			cnt += 1
	print(ct * (ct - 1) // 2 + cnt * (cnt - 1) // 2)


n = int(input())
for i in range(n):
	n = int(input())
	a = list(map(int, input().split()))[:n]
	b = 0
	b1 = 0
	for i in a:
		if i > 0:
			b += 1
		elif i < 0:
			b1 += 1
	print(b * (b - 1) // 2 + b1 * (b1 - 1) // 2)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))[:n]
	c = 0
	c1 = 0
	for i in a:
		if i > 0:
			c += 1
		elif i < 0:
			c1 += 1
	print(c * (c - 1) // 2 + c1 * (c1 - 1) // 2)


for k in range(int(input())):
	l = int(input())
	a = list(map(int, input().split()))
	count = 0
	n = [i for i in a if i < 0]
	p = [i for i in a if i > 0]
	ln = len(n)
	pn = len(p)
	print((ln * (ln - 1) + pn * (pn - 1)) // 2)


import math
t = int(input())
while t != 0:
	n = int(input())
	l = list(map(int, input().split()))
	c1 = c2 = 0
	for x in l:
		if x < 0:
			c1 += 1
		elif x > 0:
			c2 += 1
	a = b = 0
	if c1 > 1:
		a = math.factorial(c1) // (math.factorial(c1 - 2) * 2)
	if c2 > 1:
		b = math.factorial(c2) // (math.factorial(c2 - 2) * 2)
	print(a + b)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	neg = 0
	pos = 0
	for num in a:
		if num < 0:
			neg += 1
		elif num > 0:
			pos += 1
	print(int(0.5 * (neg * (neg - 1) + pos * (pos - 1))))


for T in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	c = 0
	ln = []
	lp = []
	for i in range(n):
		if li[i] > 0:
			lp.append(li[i])
		elif li[i] < 0:
			ln.append(li[i])
	cn = len(ln)
	cp = len(lp)
	c = int(cn * (cn - 1) / 2) + int(cp * (cp - 1) / 2)
	print(c)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	count1 = 0
	count2 = 0
	for i in arr:
		if i > 0:
			count1 += 1
		elif i < 0:
			count2 += 1
	print(count1 * (count1 - 1) // 2 + count2 * (count2 - 1) // 2)


t = int(input())
for dummy in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	negs = 0
	poss = 0
	pairs = 0
	for v in a:
		if v > 0:
			pairs += poss
			poss += 1
		elif v < 0:
			pairs += negs
			negs += 1
	print(pairs)


for _ in range(int(input())):
	n = int(input())
	a = map(int, input().split())
	negative = 0
	positive = 0
	for i in a:
		if i < 0:
			negative += 1
		elif i > 0:
			positive += 1
	neg_sub = negative * (negative - 1) // 2
	pos_sub = positive * (positive - 1) // 2
	print(neg_sub + pos_sub)


from math import comb
T = int(input())
for i in range(T):
	N = int(input())
	A = input().split()
	count1 = 0
	for x in range(N):
		if int(A[x]) > 0:
			count1 += 1
	count2 = 0
	for y in range(N):
		if int(A[y]) < 0:
			count2 += 1
	(a, b) = (0, 0)
	if count1 > 1:
		a = comb(count1, 2)
	if count2 > 1:
		b = comb(count2, 2)
	print(a + b)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	pos = 0
	neg = 0
	for x in l:
		if x > 0:
			pos += 1
		elif x < 0:
			neg += 1
	print(pos * (pos - 1) // 2 + neg * (neg - 1) // 2)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = 0
	y = 0
	for i in a:
		if i > 0:
			x += 1
		elif i < 0:
			y += 1
	n_x = x * (x - 1) // 2
	n_y = y * (y - 1) // 2
	print(n_x + n_y)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = 0
	y = 0
	for i in l:
		if i > 0:
			x += 1
		elif i < 0:
			y += 1
	x = x * (x - 1) // 2
	y = y * (y - 1) // 2
	print(x + y)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(pos, neg) = (0, 0)
	for i in arr:
		if i > 0:
			pos += 1
		elif i < 0:
			neg += 1
	cnt = (pos * (pos - 1) + neg * (neg - 1)) // 2
	print(cnt)


goals = int(input())
for distractions in range(goals):
	wife = int(input())
	life = list(map(int, input().split()))
	death = 0
	aim = 0
	for w in life:
		if w > 0:
			death += 1
		elif w < 0:
			aim += 1
	death = death * (death - 1) // 2
	aim = aim * (aim - 1) // 2
	print(death + aim)


import math
for _ in range(int(input())):
	n = int(input())
	string = list(map(int, input().split()))
	pos = 0
	neg = 0
	for char in string:
		if char > 0:
			pos += 1
		elif char < 0:
			neg += 1
	print(math.comb(neg, 2) + math.comb(pos, 2))


import math
for _ in range(int(input())):
	_ = input()
	arr = list(map(int, input().split(' ')))
	n_pos = 0
	n_neg = 0
	for el in arr:
		if el < 0:
			n_neg += 1
		elif el > 0:
			n_pos += 1
	res = 0
	res += math.comb(n_pos, 2)
	res += math.comb(n_neg, 2)
	print(res)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	(neg, pos) = (0, 0)
	for i in a:
		if i < 0:
			neg += 1
		elif i > 0:
			pos += 1
	print(pos * (pos - 1) // 2 + neg * (neg - 1) // 2)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	pos = sum((1 for x in a if x > 0))
	neg = sum((1 for x in a if x < 0))
	count = 0
	for i in a:
		if i > 0:
			count += pos - 1
			pos -= 1
		elif i < 0:
			count += neg - 1
			neg -= 1
	print(count)


t = int(input())
for i in range(t):
	x = int(input())
	y = list(map(int, input().split()))
	z = 0
	z1 = 0
	for j in y:
		if j > 0:
			z += 1
		elif j < 0:
			z1 += 1
	z2 = 0
	for j in range(1, z1):
		z2 += j
	for j in range(1, z):
		z2 += j
	print(z2)


def solve(n, lst):
	(neg, pos) = (0, 0)
	for i in lst:
		if i < 0:
			neg += 1
		elif i > 0:
			pos += 1
	print(neg * (neg - 1) // 2 + pos * (pos - 1) // 2)
for _ in range(int(input())):
	n = int(input())
	solve(n, list(map(int, input().split())))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	u = 0
	v = 0
	for j in range(n):
		if a[j] > 0:
			u += 1
		elif a[j] < 0:
			v += 1
	u = u * (u - 1) // 2
	v = v * (v - 1) // 2
	print(u + v)


def sumN(n):
	p = 0
	for i in range(1, n, 1):
		p += i
	return p
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	p = []
	q = []
	for i in a:
		if i < 0:
			p.append(i)
		elif i > 0:
			q.append(i)
	print(sumN(len(p)) + sumN(len(q)))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	c = 0
	po = 0
	ng = 0
	for i in range(n):
		if arr[i] > 0:
			po += 1
		elif arr[i] == 0:
			pass
		else:
			ng += 1
	c = ng * (ng - 1) // 2 + po * (po - 1) // 2
	print(c)


T = int(input())
for i in range(T):
	q = int(input())
	p = list(map(int, input().split()))
	g = 0
	h = 0
	for l in p:
		if l > 0:
			g = g + 1
		elif l < 0:
			h = h + 1
	print(g * (g - 1) // 2 + h * (h - 1) // 2)


t = int(input())
while t > 0:
	n = int(input())
	list1 = list(map(int, input().split()))
	listp = list(filter(lambda x: x > 0, list1))
	listn = list(filter(lambda x: x < 0, list1))
	val1 = len(listp) * (len(listp) - 1) // 2
	val2 = len(listn) * (len(listn) - 1) // 2
	print(val1 + val2)
	t = t - 1


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	c = 0
	d = 0
	for value in A:
		if value > 0:
			c = c + 1
		elif value < 0:
			d = d + 1
	print(c * (c - 1) // 2 + d * (d - 1) // 2)


t = int(input())
for _ in range(t):
	n = int(input())
	lis = [int(x) for x in input().split()]
	posCount = 0
	negCount = 0
	for i in range(n):
		if lis[i] > 0:
			posCount += 1
		elif lis[i] < 0:
			negCount += 1
	count = int((posCount * posCount - posCount + negCount * negCount - negCount) / 2)
	print(count)


k = int(input())
while k != 0:
	p = 0
	t = 0
	z = 0
	n = int(input())
	a = [int(i) for i in input().split()]
	for i in range(0, n):
		if a[i] > 0:
			p = p + 1
		elif a[i] < 0:
			t = t + 1
		else:
			z = z + 1
	l = t * (t - 1) // 2 + p * (p - 1) // 2
	print(l)
	k = k - 1


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	pos = 0
	neg = 0
	for i in range(len(l)):
		if l[i] > 0:
			pos += 1
		elif l[i] < 0:
			neg += 1
		else:
			pass
	print((pos - 1) * pos // 2 + (neg - 1) * neg // 2)


def Ispos(arr):
	count = 0
	stpos = -1
	stneg = -1
	cneg = 0
	for each in arr:
		if each > 0:
			stpos += 1
			count += stpos
		elif each < 0:
			stneg += 1
			cneg += stneg
	return count + cneg
t = int(input())
for i in range(t):
	l = int(input())
	arr = [int(x) for x in input().split()]
	print(Ispos(arr))