Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has a sequence $A_{1}, A_{2}, \ldots, A_{N}$. He needs to find the number of pairs $(i, j)$ ($1 ≤ i < j ≤ N$) such that $A_{i} + A_{j} = A_{i} \cdot A_{j}$. However, he is busy, so he asks for your help.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer ― the desired number of pairs.

------  Constraints ------
$1 ≤ T ≤ 20$
$1 ≤ N ≤ 40,000$
$0 ≤ A_{i} ≤ 10^{9}$ for each valid $i$

------  Subtasks ------
Subtask #1 (30 points): $1 ≤ N ≤ 500$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
2

3

2 4 2

3

0 2 3
----- Sample Output 1 ------ 
1

0
----- explanation 1 ------ 
Example case 1: The only valid pair is $(1, 3)$.

Example case 2: We can see that no valid pair exists.

Difficulty: EASY
Tags: Constructive algorithms

Combinatorics

Mathematics

Ad-hoc

Starter code:

Solutions:
import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(math.comb(a.count(2), 2) + math.comb(a.count(0), 2))


def count(n):
	return n * (n - 1) // 2
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	(b, c) = (a.count(2), a.count(0))
	print(count(b) + count(c))


import math
t = int(input())
for i in range(t):
	n = input()
	l = list(map(int, input().split()))
	zero = l.count(0)
	two = l.count(2)
	a = math.comb(zero, 2)
	b = math.comb(two, 2)
	print(a + b)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	(two, zero) = (arr.count(2), arr.count(0))
	ans = two * (two - 1) // 2 + zero * (zero - 1) // 2
	print(ans)


T = int(input())
for tc in range(T):
	N = int(input())
	l = list(map(int, input().split(' ')[:N]))
	c2 = 0
	c = 0
	for i in range(len(l)):
		if l[i] == 2:
			c2 = c2 + 1
		elif l[i] == 0:
			c = c + 1
	a = c2 * (c2 - 1) // 2
	b = c * (c - 1) // 2
	print(a + b)


import math

def nCr(n, r):
	if n <= 1:
		return 0
	f = math.factorial
	return f(n) // f(r) // f(n - r)
t = int(input())
while t != 0:
	n = int(input())
	arr = list(map(int, input().split()))
	c2 = 0
	c0 = 0
	for x in arr:
		if x == 2:
			c2 += 1
		if x == 0:
			c0 += 1
	print(nCr(c2, 2) + nCr(c0, 2))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	x = m.count(2)
	y = m.count(0)
	print(x * (x - 1) // 2 + y * (y - 1) // 2)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = a.count(2)
	y = a.count(0)
	print(x * (x - 1) // 2 + y * (y - 1) // 2)


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


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	two = l.count(2)
	zero = l.count(0)
	two = two * (two - 1) // 2
	zero = zero * (zero - 1) // 2
	print(two + zero)
	t -= 1


from math import comb
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = l.count(2)
	n = l.count(0)
	print(comb(m, 2) + comb(n, 2))


p = input()
for c in range(0, int(p)):
	n = int(input())
	a = list(map(int, input().split()))
	a0 = 0
	a2 = 0
	for xx in a:
		if xx == 0:
			a0 += 1
		elif xx == 2:
			a2 += 1
	print(a0 * (a0 - 1) // 2 + a2 * (a2 - 1) // 2)


from math import comb
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	a2 = a.count(2)
	a0 = a.count(0)
	print(comb(a2, 2) + comb(a0, 2))


from math import comb
t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	c = 0
	a2 = l.count(2)
	a0 = l.count(0)
	print(comb(a2, 2) + comb(a0, 2))


import math
t = int(input())
for i in range(t):
	N = int(input())
	st = input().split()
	n0 = 0
	n2 = 0
	for x in st:
		if x == '2':
			n2 += 1
		if x == '0':
			n0 += 1
	tot = math.comb(n2, 2) + math.comb(n0, 2)
	print(tot)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = a.count(2)
	z = a.count(0)
	tot = 0
	d = c - 1
	f = z - 1
	if c >= 2:
		while d >= 1:
			tot += d
			d -= 1
	if z >= 2:
		while f >= 1:
			tot += f
			f -= 1
	print(tot)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	o1 = a.count(2)
	o0 = a.count(0)
	c = o0 * (o0 - 1) // 2 + o1 * (o1 - 1) // 2
	print(c)


a = int(input(''))
for i in range(a):
	x = int(input(''))
	t = [int(x) for x in input('').split()]
	k = list(t)
	o1 = k.count(2)
	o2 = k.count(0)
	y = o1 * (o1 - 1) // 2 + o2 * (o2 - 1) // 2
	print(y)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	twos = a.count(2)
	zeros = a.count(0)
	print(twos * (twos - 1) // 2 + zeros * (zeros - 1) // 2)


for i in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	twos = 0
	zeros = 0
	for j in list1:
		if j == 2:
			twos += 1
		if j == 0:
			zeros += 1
	print(twos * (twos - 1) // 2 + zeros * (zeros - 1) // 2)


import math
for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	twos = a.count(2)
	zeros = a.count(0)
	tot = math.comb(twos, 2) + math.comb(zeros, 2)
	print(tot)


for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	z = lst.count(0)
	t = lst.count(2)
	count = z * (z - 1) // 2 + t * (t - 1) // 2
	print(count)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k1 = a.count(0)
	k2 = a.count(2)
	k_0 = 0
	k_2 = 0
	for i in range(k1):
		k_0 += i
	for i in range(k2):
		k_2 += i
	print(k_0 + k_2)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	x = A.count(2)
	y = A.count(0)
	print(int(x * (x - 1) / 2) + int(y * (y - 1) / 2))


for a in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	zero = array.count(0)
	two = array.count(2)
	ans = zero * (zero - 1) + two * (two - 1)
	ans = int(ans / 2)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	twos = 0
	zeroes = 0
	for i in a:
		if i == 2:
			twos += 1
		elif i == 0:
			zeroes += 1
	print(twos * (twos - 1) // 2 + zeroes * (zeroes - 1) // 2)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count_of_0 = a.count(0)
	count_of_2 = a.count(2)
	print(count_of_2 * (count_of_2 - 1) // 2 + count_of_0 * (count_of_0 - 1) // 2)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] = d[i] + 1
	count = 0
	for y in d.values():
		count = count + y * (y - 1) // 2
	print(count)


for i in range(int(input())):
	N = int(input())
	n = list(map(int, input().split()))
	sum = 0
	C = n.count(2)
	D = n.count(0)
	for j in range(1, C):
		sum += j
	for k in range(1, D):
		sum += k
	print(sum)


import math

def comb(n, r):
	if n < r:
		return 0
	f = math.factorial
	return f(n) // f(r) // f(n - r)
for i in range(int(input())):
	inp = int(input())
	nums = list(map(int, input().split()))
	zeros = nums.count(0)
	twos = nums.count(2)
	ctr = comb(zeros, 2) + comb(twos, 2)
	print(ctr)


for i in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	c = 0
	x = A.count(2)
	y = A.count(0)
	for j in range(1, x):
		c += j
	for k in range(1, y):
		c += k
	print(c)


t = int(input())
for _ in range(t):
	l = int(input())
	seq = [int(x) for x in input().split()]
	c2 = 0
	c0 = 0
	for s in seq:
		if s == 2:
			c2 += 1
		elif s == 0:
			c0 += 1
	comb = (c2 - 1) * c2 // 2 + (c0 - 1) * c0 // 2
	print(comb)


T = int(input())
for i in range(T):
	k = int(input())
	l = [int(x) for x in input().split()]
	two = l.count(2)
	z = l.count(0)
	if two + z == 0:
		print(0)
	else:
		l1 = two * (two - 1) // 2
		l2 = z * (z - 1) // 2
		print(l1 + l2)


t = int(input())
for i in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	d = L.count(2)
	e = L.count(0)
	print(e * (e - 1) // 2 + d * (d - 1) // 2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(zero, two) = (0, 0)
	for i in a:
		if i == 0:
			zero += 1
		elif i == 2:
			two += 1
	print(zero * (zero - 1) // 2 + two * (two - 1) // 2)


T = int(input())
for tc in range(T):
	N = list(map(int, input().split(' ')))
	L = list(map(int, input().split(' ')))
	count = 0
	if L.count(2) >= 2:
		count += L.count(2) * (L.count(2) - 1) // 2
	if L.count(0) >= 2:
		count += L.count(0) * (L.count(0) - 1) // 2
	print(round(count))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	a = l.count(0)
	b = l.count(2)
	print(a * (a - 1) // 2 + b * (b - 1) // 2)


def combinations(count):
	ans = 1
	for j in range(count, count - 2, -1):
		ans *= j
	denominator = 2
	return ans // denominator
tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	count = arr.count(2)
	zero_count = arr.count(0)
	ans = 0
	ans += combinations(count)
	ans += combinations(zero_count)
	print(ans)


t = int(input())
for test in range(t):
	n = int(input())
	arr = [int(char) for char in input().split()]
	a1 = arr.count(2)
	a2 = arr.count(0)
	if a1 + a2 == 0:
		print(0)
	else:
		l = a1 * (a1 - 1) // 2
		l1 = a2 * (a2 - 1) // 2
		print(l + l1)


import math
f = math.factorial
for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	z = a.count(0)
	to = a.count(2)
	z0 = 0
	t0 = 0
	if z < 2:
		z0 = 0
	else:
		z0 = f(z) / (f(2) * f(z - 2))
	if to < 2:
		t0 = 0
	else:
		t0 = f(to) / (f(2) * f(to - 2))
	ans = z0 + t0
	print(int(ans))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c1 = a.count(0)
	c2 = a.count(2)
	x = c1 * (c1 - 1) // 2 + c2 * (c2 - 1) // 2
	print(x)


T = int(input())
for t in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	c = 0
	z = a.count(2)
	y = a.count(0)
	x = z * (z - 1) // 2 + y * (y - 1) // 2
	print(x)


t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ct = 0
	z = a.count(2)
	y = a.count(0)
	r = z * (z - 1) // 2 + y * (y - 1) // 2
	print(r)


for M in range(int(input())):
	x = int(input())
	a = list(map(int, input().split()))
	m = a.count(2)
	n = a.count(0)
	print(m * (m - 1) // 2 + n * (n - 1) // 2)


ujju = int(input())
for jyo in range(ujju):
	g = int(input())
	hen = [int(i) for i in input().split()]
	l = 0
	r = 0
	for j in range(g):
		if hen[j] == 2:
			l += 1
		elif hen[j] == 0:
			r += 1
	olp = l * (l - 1) // 2 + r * (r - 1) // 2
	print(olp)


for jj in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	zc = l.count(0)
	tc = l.count(2)
	if tc <= 0 and zc <= 0:
		print('0')
	elif zc > 0 or tc > 0:
		if zc > 0:
			zc = zc * (zc - 1) // 2
		if tc > 0:
			tc = tc * (tc - 1) // 2
		print(tc + zc)


try:
	from debug import debug, timer
except ImportError:
	pass
from sys import stdin
input = stdin.readline

def rii():
	return range(int(input().strip()))

def ii():
	return int(input().strip())

def mii():
	return map(int, input().strip().split(' '))

def lmii():
	return list(map(int, input().strip().split(' ')))

def si():
	return str(input().strip())

def getvals():
	while True:
		yield from input().split()

def tri(n):
	return n * (n + 1) // 2

def solve(*args):
	(n, a) = args
	zeros = a.count(0)
	twos = a.count(2)
	return tri(zeros - 1) + tri(twos - 1)

def do_codechef():
	for t in rii():
		n = ii()
		a = lmii()
		print(solve(n, a))
do_codechef()
exit()


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


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	(temp, var) = (0, 0)
	for i in A:
		if i == 2:
			temp += 1
		elif i == 0:
			var += 1
	ans = temp * (temp - 1) // 2 + var * (var - 1) // 2
	print(ans)


test_case = int(input())
for _ in range(test_case):
	n = int(input())
	arr = list(map(int, input().split()))
	count_0 = arr.count(0)
	count_2 = arr.count(2)
	print(count_2 * (count_2 - 1) // 2 + count_0 * (count_0 - 1) // 2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c_2 = a.count(2)
	c_0 = a.count(0)
	print(c_2 * (c_2 - 1) // 2 + c_0 * (c_0 - 1) // 2)


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	c = li.count(0)
	d = li.count(2)
	if c < 2 and d < 2:
		print('0')
	else:
		x = c * (c - 1) // 2
		x += d * (d - 1) // 2
		print(x)


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	k = 0
	a = 0
	for i in range(n):
		if l[i] == 2:
			k += 1
		elif l[i] == 0:
			a += 1
	c = k * (k - 1) // 2 + a * (a - 1) // 2
	print(c)


try:
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		ans = 0
		a = 0
		b = 0
		for i in l:
			if i == 0:
				a += 1
			elif i == 2:
				b += 1
		if a > 1:
			ans += a * (a - 1) // 2
		if b > 1:
			ans += b * (b - 1) // 2
		print(ans)
except:
	pass


for _ in range(int(input())):
	validPairs = [0, 0]
	n = int(input())
	nums = list(map(int, input().split()))
	for num in nums:
		if num == 2:
			validPairs[1] = validPairs[1] + 1
		elif num == 0:
			validPairs[0] = validPairs[0] + 1
	ans = 0
	if validPairs[1] != 0:
		ans += validPairs[1] * (validPairs[1] - 1) // 2
	if validPairs[0] != 0:
		ans += validPairs[0] * (validPairs[0] - 1) // 2
	print(ans)


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	hmap = {}
	for i in arr:
		if i in hmap:
			hmap[i] += 1
		else:
			hmap[i] = 1
	ans = 0
	ans += hmap[2] * (hmap[2] - 1) // 2 if 2 in hmap else 0
	ans += hmap[0] * (hmap[0] - 1) // 2 if 0 in hmap else 0
	print(ans)


def comb(n, k):
	if n < k:
		return 0
	ans = 1
	for i in range(k + 1, n + 1):
		ans *= i
	temp = 1
	for i in range(2, n - k + 1):
		temp *= i
	return ans / temp
t = int(input())
while t:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	twos = 0
	zeros = 0
	for elem in l:
		if elem == 2:
			twos += 1
		if elem == 0:
			zeros += 1
	print(int(comb(twos, 2)) + int(comb(zeros, 2)))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count2 = 0
	count0 = 0
	for i in range(len(a)):
		if a[i] == 2:
			count2 += 1
		if a[i] == 0:
			count0 += 1
	ans = count2 * (count2 - 1) // 2 + count0 * (count0 - 1) // 2
	print(ans)


t = int(input())
while t:
	d = {}
	c2 = 0
	c0 = 0
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(n):
		if l[i] == 2:
			c2 += 1
		if l[i] == 0:
			c0 += 1
	print(c2 * (c2 - 1) // 2 + c0 * (c0 - 1) // 2)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c1 = l.count(2)
	c2 = l.count(0)
	print(c1 * (c1 - 1) // 2 + c2 * (c2 - 1) // 2)


t = int(input())
for k in range(t):
	N = int(input())
	count = 0
	A = list(map(int, input().split()))
	print(int(A.count(0) * (A.count(0) - 1) / 2 + A.count(2) * (A.count(2) - 1) / 2))