You are given an array of numbers. Let us denote the array with $\boldsymbol{A\left[\right]}$. Your task is very simple. You need to find the value returned by the function $\text{fun}(A)$.

fun(A)
    sum = 0
    for i = 1 to A.length
        for j = i+1 to A.length
            sum = sum + Floor((A[i]+A[j])/(A[i]*A[j])) 
    return sum

In short, this function takes all distinct pairs of indexes from the array and adds the value $\left\lfloor\frac{A[i]+A[j]}{A[i]\times A[j]}\right\rfloor$ to the sum. Your task is to find the sum.  

Note: $\left\lfloor\frac{A}{B}\right\rfloor$ is the integer division function.  

Input Format 

The first line contains $\mathbf{T}$, the number of test cases to follow.  

Each test case contains two lines: the first line contains $N$, the size of the array, and the second line contains $N$ integers separated by spaces.  

Output Format 

The output should contain exactly $\mathbf{T}$ lines where the $i^{th}$ line contains the answer for the $i^{th}$ test case.  

Constraints 

$1\leq T\leq15$ 

$1\leq N\leq2\times10^5$ 

$1\leq\text{Sum of}~N~\text{over all test cases}~\leq2\times10^5$ 

$1\leq A[i]\leq10^9$  

Sample Input  

2
3
4 2 3
3
1 4 1

Sample Output  

0
4

Explanation 

First Test Case: $\left\lfloor\frac{6}{8}\right\rfloor+\left\lfloor\frac{7}{12}\right\rfloor+\left\lfloor\frac{5}{6}\right\rfloor=0$ 

Second Test Case: $\left\lfloor\frac{5}{4}\right\rfloor+\left\lfloor\frac{2}{1}\right\rfloor+\left\lfloor\frac{5}{4}\right\rfloor=4$

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Matrices


Solutions:
def f(a):
	n = len(a)
	ones = a.count(1)
	twos = a.count(2)
	s = sum(a) - ones
	return ones * (ones - 1) // 2 * 2 + ones * (n - ones) + twos * (twos - 1) // 2
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(f(a))


T = int(input())
for t in range(T):
	n = int(input())
	a = list(map(int, input().split(' ')))
	(v1, v2, v3) = (0, 0, 0)
	for v in a:
		if v == 1:
			v1 += 1
		elif v == 2:
			v2 += 1
		else:
			v3 += 1
	print(v1 * (v1 - 1) + v2 * (v2 - 1) // 2 + v1 * v2 + v1 * v3)


from collections import Counter
T = int(input())
for t in range(T):
	N = int(input())
	A = map(int, input().split())
	c = Counter(A)
	print(c[1] * (N - c[1]) + c[1] * (c[1] - 1) + c[2] * (c[2] - 1) // 2)


t = int(input())
for _ in range(t):
	n = int(input())
	l = map(int, input().strip().split())
	one = 0
	two = 0
	rest = 0
	for i in l:
		if i == 1:
			one += 1
		elif i == 2:
			two += 1
		else:
			rest += 1
	ans = one * (one - 1) + one * (rest + two) + two * (two - 1) // 2
	print(ans)


T = int(input(''))
while T > 0:
	N = int(input(''))
	no = map(int, input('').split())
	ones = 0
	twos = 0
	rest = 0
	for i in no:
		if i == 1:
			ones += 1
		elif i == 2:
			twos += 1
		else:
			rest += 1
	res = 0
	res = ones * (twos + rest) + ones * (ones - 1) + twos * (twos - 1) / 2
	print(int(res))
	T -= 1


def c2(x):
	return int(x * (x - 1) / 2)

def do(i, j):
	pr = (i, j)
	if pr == (1, 1):
		return 2
	elif (i, j) == (2, 2):
		return 1
	elif i == 1 or j == 1:
		return 1
	else:
		return 0
tcs = int(input())
for i in range(tcs):
	a = int(input())
	sumx = 0
	array = list(map(int, input().split(' ')))
	ones = array.count(1)
	twos = array.count(2)
	other = a - ones - twos
	print(2 * c2(ones) + c2(twos) + (twos + other) * ones)


a = int(input())
for i in range(a):
	c = int(input())
	sum = 0
	d = input().split(' ')
	l = len(d)
	for j in range(l):
		d[j] = int(d[j])
	w = d.count(1)
	x = d.count(2)
	if w >= 1:
		sum = sum + w * (l - w)
		sum = sum + w * (w - 1)
	if x >= 1:
		sum = sum + x * (x - 1) / 2
	print(int(sum))


t = int(input())
for _ in range(t):
	input()
	ones = 0
	others = 0
	twos = 0
	for i in map(int, input().split(' ')):
		if i == 1:
			ones += 1
		elif i == 2:
			twos += 1
		else:
			others += 1
	result = ones * (others + twos) + twos * (twos - 1) // 2 + ones * (ones - 1)
	print(str(result))


t = int(input())
for t1 in range(t):
	n = int(input())
	a = [int(j) for j in input().strip().split()]
	sum = 0
	count1 = 0
	count2 = 0
	count0 = 0
	for e in a:
		if e == 1:
			count1 += 1
		elif e == 2:
			count2 += 1
		else:
			count0 += 1
	sum += count1 * (count1 - 1)
	sum += count1 * (count2 + count0)
	sum += count2 * (count2 - 1) // 2
	print(sum)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	ones = A.count(1)
	twos = A.count(2)
	total = 0
	total += ones * (N - ones)
	total += ones * (ones - 1)
	total += twos * (twos - 1) // 2
	print(total)


T = int(input())
for t in range(T):
	n = int(input())
	A = str(input()).split()
	sum = 0
	sum2 = 0
	for i in range(n):
		if int(A[i]) == 1:
			sum += 1
		if int(A[i]) == 2:
			sum2 += 1
	print(sum * (n - 1) + int(sum2 * (sum2 - 1) / 2))


def solve(num):
	for i in range(num):
		vals = int(input())
		results = list(map(int, input().split()))
		ones = results.count(1)
		others = len(results) - ones
		twos = results.count(2)
		first = ones * others
		second = ones * (ones - 1)
		third = twos * (twos - 1) // 2
		result = first + second + third
		print(result)
num = int(input())
solve(num)


def solve(A):
	lCnt = 3 * [0]
	for v in A:
		if 1 <= v <= 2:
			lCnt[v] += 1
	nbDiff1 = len(A) - lCnt[1]
	nb2 = lCnt[1] * (lCnt[1] - 1) // 2
	nb1 = lCnt[2] * (lCnt[2] - 1) // 2 + lCnt[1] * nbDiff1
	return nb2 * 2 + nb1
T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	print(solve(A))


def fast(A):
	(s, c, c2) = (0, 0, 0)
	for i in range(len(A)):
		s += c
		if A[i] == 1:
			s += i
			c += 1
		elif A[i] == 2:
			c2 += 1
	return s + c2 * (c2 - 1) // 2
for _ in range(int(input())):
	input()
	print(fast(list(map(int, input().split()))))


def pairwise_sum_divide(nlist):
	count1 = nlist.count(1)
	count2 = nlist.count(2)
	size = len(nlist)
	return count1 * (size - count1) + count1 * (count1 - 1) + count2 * (count2 - 1) // 2
t = int(input())
for i in range(t):
	n = int(input())
	ns = list(map(int, input().strip().split()))
	print(pairwise_sum_divide(ns))


def solve(A):
	countOfOnes = 0
	countOfTwos = 0
	for x in A:
		if x == 1:
			countOfOnes += 1
		elif x == 2:
			countOfTwos += 1
	countOfOthers = len(A) - countOfOnes - countOfTwos
	result = 0
	if countOfOnes > 0:
		result += (countOfOnes - 1) * countOfOnes + countOfOnes * (countOfOthers + countOfTwos)
	if countOfTwos > 1:
		result += (countOfTwos - 1) * countOfTwos // 2
	return result
for _ in range(0, int(input())):
	input()
	print(solve([int(x) for x in input().split(' ')]))


t = int(input())
for _ in range(t):
	n = int(input())
	n1 = 0
	n2 = 0
	nn = 0
	for x in input().split():
		if x == '1':
			n1 += 1
		elif x == '2':
			n2 += 1
		else:
			nn += 1
	sum = n1 * (n1 - 1)
	sum += (n1 + n2) * (n1 + n2 - 1) / 2 - sum / 2
	sum += n1 * nn
	print(int(sum))


t = int(input())
n = []
l = []
for i in range(t):
	n.append(int(input()))
	m = [int(j) for j in input().split()]
	l.append(m)
for i in l:
	u = 0
	v = 0
	s = 0
	for j in i:
		if j == 1:
			u += 1
		elif j == 2:
			s += 1
		else:
			v += 1
	ans = u * (u - 1) + s * (s - 1) // 2 + u * (s + v)
	print(ans)


import bisect
from math import factorial

def solve(A):
	A.sort()
	right = bisect.bisect_right(A, 1)
	total = 0
	if right > 0:
		total += right * (len(A) - right)
		total += right * (right - 1)
	right_2 = bisect.bisect_right(A, 2, right)
	if right_2 > right + 1:
		num = right_2 - right
		total += num * (num - 1) // 2
	return total
T = int(input())
while T > 0:
	T -= 1
	N = input()
	print(solve(list(map(int, input().split()))))


for i in range(int(input())):
	(t, a) = (input(), input().split())
	(o, n, t) = (a.count('1'), len(a) - a.count('1'), a.count('2'))
	print(o * n + o * (o - 1) + t * (t - 1) // 2)


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	ones = A.count(1)
	twos = A.count(2)
	total = 0
	total += ones * (N - ones)
	total += ones * (ones - 1)
	total += twos * (twos - 1) // 2
	print(total)


def solve(A):
	(N, n1, n2) = (len(A), 0, 0)
	for a in A:
		if a == 1:
			n1 += 1
		elif a == 2:
			n2 += 1
	return n1 * (N - n1) + 2 * n1 * (n1 - 1) // 2 + n2 * (n2 - 1) // 2
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(_) for _ in input().split()]
	print(solve(A))


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


T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	num1 = A.count(1)
	num2 = A.count(2)
	res = num1 * (N - num1) + num1 * (num1 - 1) + num2 * (num2 - 1) // 2
	print(res)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	ones = A.count(1)
	twos = A.count(2)
	total = 0
	total += ones * (N - ones)
	total += ones * (ones - 1)
	total += twos * (twos - 1) // 2
	print(total)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	ones = A.count(1)
	twos = A.count(2)
	total = 0
	total += ones * (N - ones)
	total += ones * (ones - 1)
	total += twos * (twos - 1) // 2
	print(total)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	ones = A.count(1)
	twos = A.count(2)
	total = 0
	total += ones * (N - ones)
	total += ones * (ones - 1)
	total += twos * (twos - 1) // 2
	print(total)


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(j) for j in input().split()]
	no_1 = l.count(1)
	no_2 = l.count(2)
	total = 0
	total += no_1 * (no_1 - 1)
	rem = n - no_1
	total += no_1 * rem
	total += no_2 * (no_2 - 1) // 2
	print(total)


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


from math import floor
from collections import Counter

def getsum(A):
	dic2 = Counter(A)
	keys = []
	freq = []
	for k in sorted(list(dic2.keys())):
		keys.append(k)
		freq.append(dic2[k])
	l = len(keys)
	s = 0
	for i in range(l):
		(d1, f1) = (keys[i], freq[i])
		s = s + floor(d1 * 2 / (d1 * d1)) * floor(f1 * (f1 - 1) / 2)
		if d1 > 1:
			break
		j = i + 1
		while j < l:
			(d2, f2) = (keys[j], freq[j])
			if d1 + d2 >= d1 * d2:
				q = (d1 + d2) / (d1 * d2)
				s = s + floor(q) * (f1 * f2)
				j = j + 1
			else:
				break
	return s
for t in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	print(getsum(arr))


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	num_1s = sum((num == 1 for num in array))
	num_2s = sum((num == 2 for num in array))
	print(num_2s * (num_2s - 1) // 2 + num_1s * (n - 1))


T = int(input())
for cntT in range(T):
	N = int(input())
	arr = [int(x) for x in input().split()]
	num_dict = {0: 0, 1: 0, 2: 0}
	outp = 0
	for item in arr:
		if item == 1 or item == 2:
			num_dict[item] += 1
		else:
			num_dict[0] += 1
	outp += num_dict[1] * (num_dict[1] - 1)
	outp += num_dict[1] * (num_dict[2] + num_dict[0])
	outp += num_dict[2] * (num_dict[2] - 1) >> 1
	print(outp)


T = int(input())
for t in range(0, T):
	N = int(input())
	amount_of_ones = 0
	amount_of_twos = 0
	for ch in input().split():
		x = int(ch)
		if x == 1:
			amount_of_ones += 1
		elif x == 2:
			amount_of_twos += 1
	total = 0
	total += (amount_of_ones - 1) * amount_of_ones
	total += (N - amount_of_ones) * amount_of_ones
	total += (amount_of_twos - 1) * amount_of_twos // 2
	print(total)


from collections import Counter
t = int(input())
for test in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	m = Counter(l)
	print(m[1] * (n - 1) + m[2] * (m[2] - 1) // 2)


for _ in range(int(input().strip())):
	N = int(input().strip())
	arr = map(int, input().strip().split(' '))
	ones = 0
	twos = 0
	for val in arr:
		if val == 1:
			ones += 1
		elif val == 2:
			twos += 1
	summa = ones * (N - 1) + twos * (twos - 1) // 2
	print(summa)


def do(l):
	cp1 = sum((i == 1 for i in l))
	cp2 = sum((i == 2 for i in l))
	cpa = len(l) - cp1
	return cp1 * (cp1 - 1) + cp1 * cpa + cp2 * (cp2 - 1) // 2
for _ in range(int(input().strip())):
	input()
	l = list((int(i) for i in input().strip().split()))
	print(do(l))


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


import sys

def solve(aa):
	ones = aa.count(1)
	twos = aa.count(2)
	rest = len(aa) - ones - twos
	print('aa=%s' % aa, file=sys.stderr)
	print('ones=%d twos=%d rest=%d' % (ones, twos, rest), file=sys.stderr)
	sm = ones * (ones - 1)
	sm += ones * (twos + rest)
	sm += twos * (twos - 1) // 2
	return sm
t = int(input())
for _ in range(t):
	_ = int(input())
	aa = list(map(int, input().split()))
	print(solve(aa))


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


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


T = int(input().strip())
for t in range(0, T):
	N = int(input().strip())
	A = list(map(int, input().strip().split(' ')))
	ones = A.count(1)
	twos = A.count(2)
	tot = 0
	if ones > 0:
		tot += ones * (ones - 1)
		tot += ones * (N - ones)
		if twos > 0:
			tot += twos * (twos - 1) // 2
	elif twos > 0:
		tot += twos * (twos - 1) // 2
	print(tot)


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


result = []
for _ in range(int(input())):
	(temp, half, whole, _) = (0, 0, 0, input())
	for (pos, i) in enumerate(map(int, input().split())):
		temp += whole
		if i == 1:
			temp += pos
			whole += 1
		elif i == 2:
			temp += half
			half += 1
	result.append(temp)
print(*result, sep='\n')


from itertools import combinations
T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	ones = A.count(1)
	twos = A.count(2)
	other = len(A) - ones
	print(ones * (ones - 1) + twos * (twos - 1) // 2 + other * ones)


from collections import Counter
for _ in range(int(input())):
	(n, a) = (int(input()), Counter(map(int, input().split())))
	print(a[2] * (a[2] - 1) // 2 + a[1] * (n - 1))


def answer(a):
	f1 = a.count(1)
	n = a.count(2) - 1
	triangularNumber = n * (n + 1) // 2
	if f1 == 0 and n == 0:
		return 0
	ans = (len(a) - f1) * f1
	if f1 > 1:
		ans += f1 * (f1 - 1)
	ans += triangularNumber
	return ans
for _ in range(int(input())):
	n = int(input())
	sum_ = 0
	a = list(map(int, input().split()))
	print(answer(a))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	c1 = arr.count(1)
	c2 = arr.count(2)
	print(c1 * (n - 1) + c2 * (c2 - 1) // 2)


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


for _ in range(int(input())):
	input()
	x = [0, 0, 0]
	for i in map(int, input().split()):
		if i == 1:
			x[0] += 1
		elif i == 2:
			x[1] += 1
		else:
			x[2] += 1
	r = 0
	r += x[0] * (x[0] - 1)
	r += x[0] * (x[1] + x[2])
	r += x[1] * (x[1] - 1) // 2
	print(r)


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


import sys
t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	a = [int(valore) for valore in input().strip().split(' ')]
	n1 = a.count(1)
	n2 = a.count(2)
	print((n - 1) * n1 + n2 * (n2 - 1) // 2)


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	arr = [int(i) for i in input().strip().split(' ')]
	ones = 0
	twos = 0
	for i in arr:
		if i == 1:
			ones += 1
		if i == 2:
			twos += 1
	answer = ones * (n - 1) + twos * (twos - 1) / 2
	print(int(answer))


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = [int(item) for item in input().split()]
	c2 = 0
	c1 = 0
	for i in range(n):
		if a[i] <= 2:
			if a[i] == 2:
				c2 += 1
			else:
				c1 += 1
	print(int(c1 * (n - 1) + c2 * (c2 - 1) / 2))


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


def f(x, y):
	y = (x + y) // (x * y)
	return y

def brute(a):
	s = 0
	for i in range(len(a)):
		for j in range(i + 1, len(a)):
			s += f(a[i], a[j])
	return s

def opt(a):
	ones = sum((1 for i in a if i == 1))
	twos = sum((1 for i in a if i == 2))
	n = len(a)
	s = ones * (ones - 1)
	s += ones * (n - ones)
	s += twos * (twos - 1) // 2
	return s
T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	print(opt(a))


for _ in range(int(input())):
	input()
	arr = [int(i) for i in input().split()]
	(ones, not_ones, twos) = (0, 0, 0)
	for i in arr:
		if i == 1:
			ones += 1
		else:
			not_ones += 1
			if i == 2:
				twos += 1
	print(int(ones * not_ones + ones * (ones - 1) + twos * (twos - 1) / 2))


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


def TriNum(n):
	return n * (n - 1) // 2
for __ in range(int(input())):
	input()
	A = list(map(int, input().split()))
	Ones = len(list(filter(lambda x: x == 1, A)))
	Twos = len(list(filter(lambda x: x == 2, A)))
	Others = len(A) - Ones
	print(Ones * Others + 2 * TriNum(Ones) + TriNum(Twos))


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


T = int(input())
for i in range(T):
	N = int(input())
	A = [int(a) for a in input().split()]
	A.sort()
	n_1 = A.count(1)
	n_2 = A.count(2)
	sum = n_1 * (n_1 - 1) + n_1 * (N - n_1) + n_2 * (n_2 - 1) // 2
	print(sum)


def ofun(A):
	sum = 0
	for i in range(len(A)):
		for j in range(i + 1, len(A)):
			sum = sum + (A[i] + A[j]) // (A[i] * A[j])
	return sum

def fun(A):
	count = len(A) - 1
	oneSum = sum([1 for x in A if x == 1])
	twoSum = sum([1 for x in A if x == 2])
	return oneSum * count + twoSum * (twoSum - 1) // 2
T = int(input().strip())
for _ in range(T):
	N = int(input().strip())
	A = list(map(int, input().strip().split()))
	print(fun(A))


for _ in range(int(input())):
	T = int(input())
	A = tuple(map(int, input().split()))
	res = sum(((ai == 1) * (len(A) - 1) for ai in A))
	res2 = sum((ai == 2 for ai in A))
	res += res2 * (res2 - 1) // 2
	print(res)


T = int(input())
for t in range(T):
	N = int(input())
	a = [int(i) for i in input().split()]
	pos1 = [i for i in range(N) if a[i] == 1]
	pos2 = [i for i in range(N) if a[i] == 2]
	s = 0
	if pos1:
		for i in pos1:
			s += N - 1
	if pos2:
		l = len(pos2)
		s += l * (l - 1) // 2
	print(s)


for t in range(int(input().strip())):
	n = int(input().strip())
	arr = [int(x.strip()) for x in input().split()]
	sum = 0
	count_1 = 0
	count_2 = 0
	for i in arr:
		if i == 1:
			count_1 += 1
		elif i == 2:
			count_2 += 1
	sum += (n - count_1) * count_1
	if count_1 != 0:
		sum += count_1 * (count_1 - 1)
	if count_2 != 0:
		sum += count_2 * (count_2 - 1) // 2
	print(sum)


import sys
for a0 in range(int(input())):
	N = int(input())
	res = []
	res.append(input().strip().split(' '))
	p = []
	q = 0
	for a1 in res:
		for a2 in a1:
			p.append(int(a2))
	x = p.count(1)
	y = p.count(2)
	ans = x * (N - 1) + y * (y - 1) // 2
	print(ans)


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


def f(a):
	n = len(a)
	ones = a.count(1)
	twos = a.count(2)
	return ones * (ones - 1) // 2 * 2 + ones * (n - ones) + twos * (twos - 1) // 2
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(f(a))


for t in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	other = 0
	two = 0
	one = 0
	ans = 0
	for i in l:
		if i == 1:
			one += 1
		if i == 2:
			two += 1
		if i != 1:
			other += 1
	if one != 0 and two > 1:
		ans = other * one + one * (one - 1) + two * (two - 1) // 2
	elif one != 0:
		ans = other * one + one * (one - 1)
	elif two > 1:
		ans = two * (two - 1) // 2
	print(ans)


t = int(input())
while t > 0:
	t -= 1
	ret = 0
	n = int(input())
	vals = [int(x) for x in input().split()]
	ones = 0
	twos = 0
	for i in range(n):
		if vals[i] == 1:
			ones += 1
		elif vals[i] == 2:
			twos += 1
	print(ones * (n - 1) + twos * (twos - 1) // 2)


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


import math

def bino(a, b):
	return math.factorial(a) // (math.factorial(a - b) * math.factorial(b))

def f(A):
	A = sorted(A)
	count1 = 0
	count2 = 0
	for i in range(len(A)):
		if A[i] == 1:
			count1 += 1
		if A[i] == 2:
			count2 += 1
	ans = 0
	ans = count1 * (count1 - 1) + count1 * (len(A) - count1)
	ans += count2 * (count2 - 1) // 2
	return ans
for _ in range(int(input())):
	input()
	print(f(list(map(int, input().strip().split(' ')))))


for _ in range(int(input())):
	n = int(input())
	A = [int(a) for a in input().strip().split(' ')]
	count1 = 0
	count2 = 0
	for i in range(n):
		if A[i] == 1:
			count1 += 1
		elif A[i] == 2:
			count2 += 1
	result = 2 * (count1 * (count1 - 1) // 2) + count1 * (n - count1) + count2 * (count2 - 1) // 2
	print(result)


import math
n = int(input().strip())
for i in range(n):
	ar_size = int(input().strip())
	if ar_size == 1:
		print(int(0))
	else:
		ar = list(map(int, input().strip().split(' ')))
		ar_2 = [a for a in ar if a == 2]
		ar_2_size = len(ar_2)
		print(int(sum([ar_size - 1 for a in ar if a == 1]) + ar_2_size * (ar_2_size - 1) / 2))


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	A = list(map(int, input().strip().split()))
	(p, q) = (A.count(1), A.count(2))
	print(p * (n - 1) + q * (q - 1) // 2)


for i in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	count_1 = 0
	count_2 = 0
	for x in ar:
		if x == 1:
			count_1 += 1
		elif x == 2:
			count_2 += 1
	print(count_1 * (n - 1) + count_2 * (count_2 - 1) // 2)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	ones = a.count(1)
	twos = a.count(2)
	notones = len(a) - ones
	sum = ones * (ones - 1) + twos * (twos - 1) // 2 + ones * notones
	print(sum)


import sys
import math

def pairwise_sum_divide(A):
	positive_numbers = 0
	negative_numbers = 0
	positive_ones = 0
	negative_ones = 0
	positive_twos = 0
	negative_twos = 0
	for n in A:
		n = int(n)
		if n > 0:
			positive_numbers += 1
			if n == 1:
				positive_ones += 1
			elif n == 2:
				positive_twos += 1
		else:
			negative_numbers += 1
			if n == -1:
				negative_ones += 1
			elif n == -2:
				negative_twos += 1
	return positive_ones * (positive_numbers - 1) - negative_ones * (negative_numbers - 1) + (positive_twos * positive_twos - positive_twos >> 1) - (negative_twos * negative_twos - negative_twos >> 1)
T = input().strip().split(' ')
for test_case in range(int(T[0])):
	N = input().strip().split(' ')
	A = input().strip().split(' ')
	print(pairwise_sum_divide(A))


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	c = a.count(1)
	c2 = a.count(2)
	print(c * (n - c + 2 * (c - 1)) - c * (c - 1) + c2 * (c2 - 1) // 2)


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


k = int(input().strip())
for i in range(k):
	n = int(input().strip())
	ar = list(map(int, input().strip().split(' ')))
	x = ar.count(1)
	y = ar.count(2)
	z = y * (y - 1) // 2
	print(x * (n - 1) + z)


q = int(input())
for i in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	n1 = 0
	k = 0
	for i in range(n):
		if arr[i] == 1:
			n1 = n1 + 1
		if arr[i] == 2:
			k = k + 1
	m = n - n1
	ans = m * n1 + n1 * (n1 - 1) + k * (k - 1) / 2
	print(int(ans))


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	ones = A.count(1)
	twos = A.count(2)
	total = 0
	total += ones * (N - ones)
	total += ones * (ones - 1)
	total += twos * (twos - 1) // 2
	print(total)


T = int(input())
for i in range(0, T):
	N = int(input())
	A = [int(a) for a in input().split()]
	m = 0
	l = 0
	for j in range(0, N):
		if A[j] == 1:
			m += 1
		if A[j] == 2:
			l += 1
	print(m * (N - 1) + l * (l - 1) // 2)


def f():
	input()
	return input().split()
N = int(input())
L = (list(map(int, f())) for _ in range(N))
for x in L:
	(s, t) = (len([z for z in x if z == a]) for a in (1, 2))
	l = len(x)
	print(s * (s - 1) + s * (l - s) + t * (t - 1) // 2)


def solution(A):
	(ones, twos) = (A.count(1), A.count(2))
	not_ones = len(A) - ones
	return ones * (ones - 1 + not_ones) + twos * (twos - 1) // 2
for _ in range(int(input().strip())):
	N = int(input().strip())
	print(solution([int(x) for x in input().strip().split(' ')]))


from collections import Counter
nt = int(input())
for _ in range(nt):
	n = int(input())
	ctr = Counter(map(int, input().split()))
	print(ctr[2] * (ctr[2] - 1) // 2 + ctr[1] * (n - 1))


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


from collections import Counter
for _ in range(int(input())):
	(n, A) = (int(input()), Counter(map(int, input().split())))
	print(A[2] * (A[2] - 1) // 2 + A[1] * (n - 1))


def fun(a):
	s = 0
	a.sort()
	for i in range(len(a)):
		for j in range(i + 1, len(a)):
			r = (a[i] + a[j]) // (a[i] * a[j])
			s += r
			if r != 0:
				print(r, s, a[i], a[j])
	return s

def r(a):
	ones = sum((1 for i in a if i == 1))
	twos = sum((1 for i in a if i == 2))
	r = ones * (len(a) - 1)
	r += twos * (twos - 1) // 2
	return r
for _ in range(int(input())):
	_ = int(input())
	a = list(map(int, input().split()))
	print(r(a))