You are given an array A containing N positive integers. Find the number of pairs (i,j) such that 1 ≤ i < j ≤ N and:
A_{i} + A_{j} ≥ A_{i} \cdot A_{j}

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

- The first line contains an integer T denoting the number of test cases. The T test cases then follow.
- The first line of each test case contains an integer N.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.

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

For each test case, output on a new line the required answer.

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

$1 ≤T ≤1000$
$2 ≤N ≤2 \cdot 10^{5}$
$1 ≤A_{i} ≤10^{6}$
- Sum of $N$ over all cases won't exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
2
3
1 3 4
5
2 3 4 5 6
----- Sample Output 1 ------ 
2
0
----- explanation 1 ------ 
Test case $1$: The two pairs are $(1, 2)$ and $(1, 3)$, because:
- $A_{1} + A_{2} = 4 > 3 = A_{1} \cdot A_{2}$
- $A_{1} + A_{3} = 5 > 4 = A_{1} \cdot A_{3}$

Test case $2$: No pairs satisfy the condition.

Source: codechef | Difficulty: EASY


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


from math import comb
from collections import Counter
t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	d = Counter(l)
	c1 = l.count(1)
	c2 = l.count(2)
	print((len(l) - c1) * c1 + comb(c2, 2) + comb(c1, 2))


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


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	(a1, a2) = (a.count(1), a.count(2))
	print(a1 * (n - 1) - a1 * (a1 - 1) // 2 + a2 * (a2 - 1) // 2)


from math import comb
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = l.count(1)
	b = l.count(2)
	print(int(a * (n - a) + b * (b - 1) / 2 + a * (a - 1) / 2))


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


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


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


T = int(input())
for i in range(T):
	sum = 0
	n = int(input())
	l = input().split()
	count = 0
	for i in range(n):
		if l[i] == '1':
			sum += n - count - 1
			count += 1
	m = l.count('2')
	if m > 1:
		sum = sum + m * (m - 1) / 2
	print(int(sum))


tt = int(input())
for _ in range(tt):
	g = int(input())
	arr = [int(i) for i in input().split()]
	arr.sort()
	p1 = arr.count(1)
	p2 = arr.count(2)
	ans = p1 * g - (p1 + 1) * p1 // 2 + (p2 - 1) * p2 // 2
	print(ans)


tc = int(input())
for _ in range(tc):
	n = int(input())
	arr = [int(x) for x in input().split()]
	count_1 = 0
	count_2 = 0
	for x in arr:
		if x == 1:
			count_1 += 1
		elif x == 2:
			count_2 += 1
	if n - count_1 - count_2 > 0:
		result = count_1 * (count_1 - 1) // 2 + count_2 * (count_2 - 1) // 2 + count_1 * (n - count_1 - count_2) + count_1 * count_2
	else:
		result = count_1 * count_2 + count_1 * (count_1 - 1) // 2 + count_2 * (count_2 - 1) // 2
	print(result)


for i in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	o = a.count(1)
	z = a.count(2)
	ans = o * (n - o)
	ans += o * (o - 1) // 2
	ans += z * (z - 1) // 2
	print(ans)


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


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ctr = Counter()
	res = 0
	for i in range(n):
		if arr[i] > 2:
			res += ctr[1]
		elif arr[i] == 2:
			res += ctr[1] + ctr[2]
		else:
			res += i
		ctr[arr[i]] += 1
	print(res)


T = int(input())
pairs = []
for j in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	ones = A.count(1)
	onepairs = ones * (N - 1) - ones * (ones - 1) / 2
	twos = A.count(2)
	twopairs = twos * (twos - 1) / 2
	total = int(onepairs + twopairs)
	pairs.append(total)
for count in range(T):
	print(pairs[count])


t = int(input(''))
nsum = 0
if 1 <= t <= 1000:
	for _ in range(t):
		n = int(input(''))
		a = input().split()
		nsum += n
		if 2 <= n <= 2 * 10 ** 5 and len(a) == n and (nsum <= 2 * 10 ** 5):
			for i in range(n):
				a[i] = int(a[i])
			x = a.count(1)
			sum = n * x - x * (x + 1) // 2
			y = a.count(2)
			if y >= 2:
				sum += y * (y - 1) // 2
			print(sum)


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


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


T = int(input())
while T > 0:
	N = int(input())
	A = list(map(int, input().strip().split()))[:N]
	ones = 0
	twos = 0
	for i in range(N):
		if A[i] == 1:
			ones += 1
		elif A[i] == 2:
			twos += 1
	c = ones * (ones - 1) // 2 + ones * (N - ones) + twos * (twos - 1) // 2
	print(c)
	T -= 1


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


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


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


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	ones_count = arr.count(1)
	twos_count = arr.count(2)
	ans = ones_count * (length - ones_count)
	if ones_count > 1:
		ones_count -= 1
		ans += ones_count * (ones_count + 1) // 2
	if twos_count > 1:
		twos_count -= 1
		ans += twos_count * (twos_count + 1) // 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	ans = 0
	oc = l.count(1)
	ow = l.count(2)
	ans = oc * (n - oc)
	ans += oc * (oc - 1) // 2
	ans += ow * (ow - 1) // 2
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s = input().split()
	arr = []
	for el in s:
		arr.append(int(el))
	ones = 0
	twoes = 0
	for el in arr:
		if el == 1:
			ones += 1
		if el == 2:
			twoes += 1
	ta = n * (n - 1) // 2 - (n - ones - 1) * (n - ones) // 2
	tb = int(twoes * (twoes - 1) / 2)
	print(ta + tb)


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


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


t = int(input())
for i in range(t):
	n = int(input())
	d = list(map(int, input().strip().split()))[:n]
	a = d.count(1)
	b = d.count(2)
	ans = a * (n - a)
	ans += a * (a - 1) // 2
	ans += b * (b - 1) // 2
	print(ans)


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


def solve(arr, n):
	ones = arr.count(1)
	twos = arr.count(2)
	ans = ones * (n - ones)
	ans += ones * (ones - 1) // 2
	ans += twos * (twos - 1) // 2
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(arr, n))


a = int(input())
for i in range(0, a, 1):
	count = 0
	count1 = 0
	r = 0
	b = int(input())
	c = input()
	d = c.split()
	for i in range(0, b, 1):
		if int(d[i]) == 2:
			count += 1
		if int(d[i]) == 1:
			count1 += 1
		r = count1 * len(d)
		r -= count1 * (count1 + 1) / 2
		r += count * (count - 1) / 2
	print(int(r))


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	x = a.count(1)
	ans += n * x - (x + 1) * x // 2
	y = a.count(2)
	ans += y * (y - 1) // 2
	print(ans)
	t = t - 1


import sys
import math
import bisect
import heapq
from bisect import bisect_right
from sys import stdin, stdout

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(sys.stdin.readline())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def myceil(x, y):
	return (x + y - 1) // y

def Solution():
	pass

def main():
	for _ in range(get_int()):
		n = get_int()
		a = get_ints_in_list()
		cntOne = a.count(1)
		cntTwo = max(1, a.count(2))
		t = n - 1
		ans = 0
		while cntOne:
			ans += t
			t -= 1
			cntOne -= 1
		ans += cntTwo * (cntTwo - 1) // 2
		print(ans)
main()


for i in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	c1 = 0
	c2 = 0
	res = 0
	for j in range(n):
		if l[j] == 1:
			c1 += 1
		if l[j] == 2:
			c2 += 1
	res = c1 * (n - c1)
	if c1 > 1:
		res += c1 * (c1 - 1) // 2
	if c2 > 1:
		res += c2 * (c2 - 1) // 2
	print(res)


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


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	p = a.count(1)
	c = p * (n - 1) - p * (p - 1) // 2
	k = a.count(2)
	if k > 1:
		c += k * (k - 1) // 2
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(input().split())
	nums = []
	for i in l:
		nums.append(int(i))
	n1 = 0
	n2 = 0
	for i in nums:
		if i == 1:
			n1 += 1
		elif i == 2:
			n2 += 1
	n1dot = n - n1
	print(n1 * n1dot + n1 * (n1 - 1) // 2 + n2 * (n2 - 1) // 2)


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


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')

def solve():
	for _ in range(get_int()):
		n = get_int()
		arr = get_list()
		ans = 0
		count = 0
		for i in range(n):
			if arr[i] == 1:
				ans += 1
			elif arr[i] == 2:
				count += 1
		get_print_int(ans * (n - ans) + ans * (ans - 1) // 2 + count * (count - 1) // 2)
solve()


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


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


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


a = int(input())
for x in range(a):
	b = int(input())
	c = list(map(int, input().split()))
	one = [0]
	two = [0]
	for y in range(b):
		if c[y] == 1:
			one.append(one[y] + 1)
		else:
			one.append(one[y])
		if c[y] == 2:
			two.append(two[y] + 1)
		else:
			two.append(two[y])
	ans = 0
	for y in range(b):
		if c[y] == 1:
			ans += b - (y + 1)
		elif c[y] == 2:
			ans += one[-1] - one[y + 1] + (two[-1] - two[y + 1])
		else:
			ans += one[-1] - one[y + 1]
	print(ans)


def solve(arr, n):
	c1 = arr.count(1)
	c2 = arr.count(2)
	return c1 * (n - c1) + c1 * (c1 - 1) // 2 + c2 * (c2 - 1) // 2
t = int(input())
while t > 0:
	n = int(input())
	all = [int(i) for i in input().split()]
	print(solve(all, n))
	t -= 1


try:
	t = int(input())
	for i in range(0, t):
		numero_de_entradas = int(input())
		entradas = [int(num) for num in input().split(' ')]
		unos = 0
		doses = 0
		for entrada in entradas:
			if entrada == 1:
				unos += 1
			if entrada == 2:
				doses += 1
		number_of_pairs = unos * (numero_de_entradas - unos) + unos * (unos - 1) // 2 + doses * (doses - 1) // 2
		print(number_of_pairs)
except Exception as e:
	print(e)


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


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


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


T = int(input().strip())
for i in range(T):
	N = int(input().strip())
	L = list(map(int, input().strip().split(' ')))
	c1 = L.count(1)
	c2 = L.count(2)
	print(c1 * (N - c1) + c1 * (c1 - 1) // 2 + c2 * (c2 - 1) // 2)


t = int(input())
while t:
	n = int(input())
	x = list(map(int, input().split()))
	c1 = 0
	c0 = 0
	for i in x:
		if i == 1:
			c0 += 1
		if i == 2:
			c1 += 1
	print(c0 * n - sum(range(c0 + 1)) + c1 * (c1 - 1) // 2)
	t = t - 1


iterations = int(input())
for iteration in range(iterations):
	itemcount = int(input())
	totalpass = 0
	items = list(map(int, input().split()))
	ones = items.count(1)
	totalpass += sum(list(range(itemcount - ones, itemcount)))
	twos = items.count(2)
	totalpass += sum(list(range(twos)))
	print(totalpass)


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


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


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


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = a.count(1)
	c = a.count(2)
	print(b * (b - 1) // 2 + (n - b) * b + c * (c - 1) // 2)


t = int(input())
for _ in range(t):
	l = int(input())
	arr = list(map(int, input().split()))
	one = 0
	two = 0
	com = 0
	for i in arr:
		if i == 1:
			one += 1
		elif i == 2:
			two += 1
	com += (l - one) * one
	com += (two - 1) * two // 2
	com += (one - 1) * one // 2
	print(com)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	d = 0
	for i in range(0, len(l)):
		if l[i] == 1:
			c = c + 1
		elif l[i] == 2:
			d = d + 1
	q = (d * d - d) // 2
	r = c * (2 * n - 1) - c * c
	print(r // 2 + q)


t = int(input())
for _ in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	c1 = 0
	c2 = 0
	for i in range(0, N):
		if A[i] == 1:
			c1 += 1
		elif A[i] == 2:
			c2 += 1
	ans = c1 * (N - c1) + c1 * (c1 - 1) // 2 + c2 * (c2 - 1) // 2
	print(ans)


for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	c = 0
	b = 0
	for i in l:
		if i == 1:
			c += 1
		elif i == 2:
			b += 1
	if c == 0 and b == 0:
		print(0)
	else:
		k = c * (2 * x - 1) - c * c
		k = k // 2
		k += b * (b - 1) // 2
		print(k)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	c1 = 0
	c2 = 0
	for i in range(0, n):
		if arr[i] == 1:
			c1 += 1
		elif arr[i] == 2:
			c2 += 1
	ans = c1 * (n - c1) + c1 * (c1 - 1) // 2 + c2 * (c2 - 1) // 2
	print(ans)


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


t = int(input())
for i in range(t):
	count = 0
	N = int(input())
	lst = [int(i) - 1 for i in input().split()]
	n = len(lst)
	x = lst.count(0)
	y = lst.count(1)
	print(int(x * (n - x) + x * (x - 1) / 2 + y * (y - 1) / 2))


def solve(n, arr):
	ones = twos = 0
	res = 0
	for i in range(n):
		if arr[i] == 1:
			res += n - i - 1
			res += i - ones
			ones += 1
		elif arr[i] == 2:
			res += twos
			twos += 1
	return res
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(solve(n, arr))