Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

You are given an integer sequence $A$ with length $N$.

Find the number of (unordered) pairs of elements such that the average of these two elements is also present in the sequence. Formally, find the number of pairs $(i,j)$ such that $1 ≤ i < j ≤ N$ and there is an index $k$ ($1 ≤ k ≤ N$) for which $2A_{k} = A_{i}+A_{j}$ holds.

------  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}, \dots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer — the number of valid pairs $(i,j)$.

------  Constraints  ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$|A_{i}| ≤ 10^{3}$ for each valid $i$

------  Subtasks ------

Subtask #1 (30 points): $1 ≤ N ≤ 10^{3}$

Subtask #2 (70 points): $1 ≤ N ≤ 10^{5}$

----- Sample Input 1 ------ 
3
2
2 2
3
2 1 3
6
4 2 5 1 3 5
----- Sample Output 1 ------ 
1
1
7
----- explanation 1 ------ 
Example case 1: We can take $k$ for $A_{k}$ to be either 1 or 2, since $A_{k}=2$ either way. Since the problem asks for unordered pairs, $(1,2)$ is the only possible valid pair (the same as $(2,1)$). Hence, the answer is 1.

Example case 2: We see that $A_{1} = 2 = (1+3)/2$. No other valid pair exists.

Difficulty: MEDIUM_HARD
Tags: Data structures

Mathematics
Skill types: Data structures

Starter code:

Solutions:
def ti():
	return tuple(map(int, input().split()))

def li():
	return list(map(int, input().split()))

def si():
	return input().split()

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

def ip():
	return input()
for tastcas in range(int(input())):
	n = ii()
	a = li()
	d = {}
	ans = 0
	for i in range(-1000, 1001):
		d[i] = 0
	for i in a:
		d[i] += 1
	for i in range(-1000, 1001):
		for j in range(i, 1001, 2):
			if i == j:
				x = (i + j) / 2
				if d[x]:
					ans += d[i] * (d[i] - 1) // 2
			else:
				x = (i + j) // 2
				if d[x]:
					ans += d[i] * d[j]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	f = [0] * 2001
	for i in a:
		f[i] += 1
	(ans1, ans2) = (0, 0)
	for i in range(-1000, 1001, 1):
		if f[i] != 0:
			for j in range(i, 1001, 2):
				if f[j] != 0:
					if i == j:
						ans1 += f[i] * (f[i] - 1) // 2
					elif (i + j) % 2 == 0 and f[(i + j) // 2] != 0:
						ans2 += f[i] * f[j]
	print(ans1 + ans2)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in range(-1000, 1001):
		d[i] = 0
	for i in l:
		d[i] += 1
	ans = 0
	for i in range(-1000, 1001):
		for j in range(i, 1001, 2):
			if i == j:
				x = (i + j) / 2
				if d[x]:
					ans += d[i] * (d[i] - 1) // 2
			else:
				x = (i + j) // 2
				if d[x]:
					ans += d[i] * d[j]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	c = 0
	x = max(l)
	for j in range(-1000, 1001):
		d[j] = 0
	for j in l:
		d[j] += 1
	for j in range(-1000, 1001):
		k = j
		while k <= 1000:
			if j == k:
				z = (j + k) // 2
				if d[z]:
					c += d[j] * (d[k] - 1) // 2
			else:
				z = (j + k) // 2
				if d[z]:
					c += d[j] * d[k]
			k += 2
	print(c)


from collections import Counter
t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	count = 0
	x = max(l)
	for i in range(-1000, 1001):
		d[i] = 0
	for i in l:
		d[i] += 1
	for i in range(-1000, 1001):
		j = i
		while j <= 1000:
			if i == j:
				k = (i + j) // 2
				if d[k]:
					count += d[i] * (d[j] - 1) // 2
			else:
				k = (i + j) // 2
				if d[k]:
					count += d[i] * d[j]
			j += 2
	print(count)
	t -= 1


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = defaultdict(int)
	f = defaultdict(int)
	for i in range(n):
		d[2 * (a[i] + 1000)] = 1
		f[a[i] + 1000] += 1
	k = 0
	ans = 0
	keys = list(f.keys())
	for i in keys:
		ans += f[i] * (f[i] - 1) // 2
		k += 1
		for j in keys[k:]:
			if d[i + j]:
				ans += f[i] * f[j]
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [0 for j in range(2001)]
	zz = 0
	for num in a:
		b[num] += 1
	for num in range(-1000, 1001):
		if b[num] == 0:
			continue
		if b[num] > 1:
			zz += b[num] * (b[num] - 1) / 2
		high_num = num
		low_num = num
		while True:
			high_num += 1
			low_num -= 1
			if high_num > 1000 or low_num < -1000:
				break
			zz += b[high_num] * b[low_num]
	print(int(zz))


def mi():
	return map(int, input().split())
for _ in range(int(input())):
	n = int(input())
	a = list(mi())
	ans = 0
	v = list(set(a))
	c = {i: 0 for i in range(-1000, 1001)}
	for i in a:
		c[i] += 1
	for i in range(-1000, 1001):
		if not c[i]:
			continue
		ans += c[i] * (c[i] - 1) // 2
		x = 1
		while i - x >= -1000 and i + x <= 1000:
			ans += c[i - x] * c[i + x]
			x += 1
	print(ans)


for i in range(int(input())):
	d = {}
	n = int(input())
	for i in range(0, 2001):
		d[i] = 0
	l = list(map(int, input().split()))
	for i in range(n):
		l[i] = l[i] + 1000
		d[l[i]] += 1
	ans = 0
	for mid in range(2001):
		if d[mid] == 0:
			continue
		ans += d[mid] * (d[mid] - 1) // 2
		x = 1
		while mid - x >= 0 and mid + x <= 2000:
			ans += d[mid - x] * d[mid + x]
			x += 1
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	l = [0 for i in range(200011)]
	A = list(map(int, input().split()))
	for i in A:
		l[1000 + i] += 1
	s = 0
	for i in range(2001):
		for j in range(i, 2001, 2):
			if l[(i + j) // 2] != 0:
				if i == j:
					s += l[i] * (l[i] - 1) // 2
				else:
					s += l[i] * l[j]
	print(s)


T = int(input())
for t in range(T):
	N = int(input())
	i = 0
	f = [0 for i in range(2 * 1000 + 2)]
	A = list(map(int, input().split()))
	for i in range(N):
		f[A[i] + 1000] += 1
	ct = 0
	for i in range(2 * 1000 + 2):
		for j in range(i + 1, 2 * 1000 + 2):
			if f[(i + j) // 2] > 0 and (i + j) % 2 == 0:
				ct += f[i] * f[j]
		if f[i] > 1:
			ct += (f[i] - 1) * f[i] // 2
	print(ct)


_ = int(input())
for __ in range(_):
	N = int(input())
	A = [int(x) + 1000 for x in input().split()]
	f = [0] * 2001
	ans = 0
	for i in A:
		f[i] += 1
	for i in range(2001):
		if f[i] != 0:
			for j in range(i + 2, 2001, 2):
				if f[j] != 0:
					if f[(i + j) // 2] != 0:
						ans += f[i] * f[j]
			ans += (f[i] - 1) * f[i] // 2
	print(ans)


t = int(input())
for i in range(0, t):
	n = int(input())
	l = []
	no = input().split()
	for i2 in no:
		l.append(int(i2) + 1000)
	c = [0 for val in range(0, 2001)]
	for i2 in l:
		c[i2] += 1
	tc = 0
	for j in range(0, 1999):
		if c[j]:
			if c[j] > 1:
				tc += c[j] * (c[j] - 1) // 2
			for j2 in range(j + 2, 2001, 2):
				if c[(j + j2) // 2]:
					tc += c[j] * c[j2]
	print(tc)


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	freq = [0] * 2001
	for i in range(n):
		freq[l[i] + 1000] += 1
	count = 0
	for i in range(2001):
		count += freq[i] * (freq[i] - 1) // 2
		for j in range(i + 2, 2001, 2):
			if freq[(i + j) // 2]:
				count += freq[i] * freq[j]
	print(count)


q = int(input())
for i in range(q):
	n = int(input())
	ls = list(map(int, input().split()))
	c = [0] * 2001
	for j in ls:
		c[j + 1000] += 1
	ans = 0
	for j in range(2001):
		ans += c[j] * (c[j] - 1) // 2
		for k in range(j + 2, 2001, 2):
			if c[(j + k) // 2]:
				ans += c[j] * c[k]
	print(ans)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	k = Counter(lis)
	j = list(k.keys())
	l = list(k.values())
	count = 0
	doub = set([x << 1 for x in j])
	for x in range(len(j)):
		count += l[x] * (l[x] - 1) >> 1
		for q in range(x + 1, len(j)):
			if j[x] + j[q] in doub:
				count += l[x] * l[q]
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	k = 0
	d = [0] * 2100
	for x in arr:
		d[x + 1000] += 1
	for i in range(1999):
		if d[i] != 0:
			for j in range(i + 2, 2004, 2):
				if d[j] != 0:
					if d[(i + j) // 2] != 0:
						k += d[i] * d[j]
			k += (d[i] - 1) * d[i] // 2
	print(k)


for i in range(int(input())):
	n = int(input())
	ev = []
	od = []
	c = 0
	p = list(map(int, input().split()))
	arr = [0] * 2005
	for j in range(n):
		arr[p[j] + 1000] += 1
	for k in range(0, 1999):
		if arr[k] != 0:
			for p in range(k + 2, 2004, 2):
				if arr[p] != 0:
					if arr[int((k + p) / 2)] != 0:
						c += arr[p] * arr[k]
			c += (arr[k] - 1) * arr[k] / 2
	print(int(c))


def countpair(hasharr, ar):
	count = 0
	for i in range(len(ar) - 1):
		a = ar[i]
		if a < 0:
			f = hasharr[1000 + abs(a)]
		else:
			f = hasharr[a]
		for j in ar[i + 1:]:
			b = j
			num = (a + b) // 2
			if num < 0:
				num = 1000 + abs(num)
			if b < 0:
				g = hasharr[1000 + abs(b)]
			else:
				g = hasharr[b]
			if hasharr[num] >= 1:
				h = f * g
				count += h
	return count

def selfcount(hasharr, ar):
	co = 0
	for i in ar:
		if i < 0:
			i = 1000 + abs(i)
		if hasharr[i] >= 2:
			a = hasharr[i]
			b = a * (a - 1) // 2
			co += b
	return co
for z in range(int(input())):
	n = int(input())
	ar = [int(x) for x in input().split()]
	k = [0 for i in range(2001)]
	even = []
	odd = []
	for i in ar:
		if i < 0:
			k[1000 + abs(i)] += 1
		else:
			k[i] += 1
	for j in range(2001):
		if k[j] != 0:
			if j % 2 == 0:
				if j < 1001:
					even.append(j)
				else:
					even.append(1000 - j)
			elif j < 1001:
				odd.append(j)
			else:
				odd.append(1000 - j)
	xx = countpair(k, even)
	y = countpair(k, odd)
	p = selfcount(k, odd)
	q = selfcount(k, even)
	print(xx + y + p + q)


t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	a = [int(x) for x in input().strip().split(' ')]
	b = [0] * 1000001
	m = 0
	for i in range(n):
		b[a[i]] += 1
	c = []
	d = []
	p = 0
	q = 0
	s = 0
	h = set(a)
	h = list(h)
	for i in range(len(h)):
		if h[i] % 2:
			c.append(h[i])
			p += 1
		else:
			d.append(h[i])
			q += 1
	if c != []:
		for i in range(p - 1):
			for j in range(i + 1, p):
				if b[int((c[i] + c[j]) / 2)]:
					s += b[c[i]] * b[c[j]]
			s += int(b[c[i]] * (b[c[i]] - 1) / 2)
		s += int(b[c[p - 1]] * (b[c[p - 1]] - 1) / 2)
	if d != []:
		for i in range(q - 1):
			for j in range(i + 1, q):
				if b[int((d[i] + d[j]) / 2)]:
					s += b[d[i]] * b[d[j]]
			s += int(b[d[i]] * (b[d[i]] - 1) / 2)
		s += int(b[d[q - 1]] * (b[d[q - 1]] - 1) / 2)
	print(s)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	Ad = Counter(A)
	B = list(Ad.keys())
	BF = list(Ad.values())
	BS = set([b << 1 for b in B])
	(otpt, m) = (0, len(B))
	for i in range(m):
		(a0, a1f) = (B[i], BF[i])
		otpt += a1f * (a1f - 1) >> 1
		for j in range(i + 1, m):
			a1 = a0 + B[j]
			if a1 in BS:
				otpt += a1f * BF[j]
	print(otpt)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	oddS = set()
	oddD = {}
	evenS = set()
	evenD = {}
	for a in A:
		if a % 2 == 0:
			evenS.add(a)
			if a in evenD:
				evenD[a] += 1
			else:
				evenD[a] = 1
		else:
			oddS.add(a)
			if a in oddD:
				oddD[a] += 1
			else:
				oddD[a] = 1
	evenS = list(evenS)
	oddS = list(oddS)
	double = set([2 * x for x in list(set(A))])
	count = 0
	for i in range(len(evenS) - 1):
		for j in range(i + 1, len(evenS)):
			if evenS[i] != evenS[j] and evenS[i] + evenS[j] in double:
				count += evenD[evenS[i]] * evenD[evenS[j]]
	for i in range(len(oddS) - 1):
		for j in range(i + 1, len(oddS)):
			if oddS[i] != oddS[j] and oddS[i] + oddS[j] in double:
				count += oddD[oddS[i]] * oddD[oddS[j]]
	for a in evenS:
		if evenD[a] > 1 and 2 * a in double:
			count += evenD[a] * (evenD[a] - 1) / 2
	for a in oddS:
		if oddD[a] > 1 and 2 * a in double:
			count += oddD[a] * (oddD[a] - 1) / 2
	print(int(count))


import operator as op
import functools

def ncr(n, r):
	r = min(r, n - r)
	numer = functools.reduce(op.mul, range(n, n - r, -1), 1)
	denom = functools.reduce(op.mul, range(1, r + 1), 1)
	return numer // denom

def findPairs(arr, n):
	s = set()
	d = {}
	val = 0
	for x in arr:
		s.add(2 * x)
	for x in arr:
		if x not in d:
			d[x] = 1
		else:
			d[x] += 1
	set1 = set(arr)
	arr1 = list(set1)
	arr1.sort()
	for i in range(len(arr1) - 1):
		for j in range(i + 1, len(arr1)):
			sum = arr1[i] + arr1[j]
			if sum in s:
				val += d[arr1[i]] * d[arr1[j]]
	for x in arr1:
		if d[x] > 1:
			val += ncr(d[x], 2)
	print(val)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	mi = min(l)
	for x in l:
		x -= mi
	findPairs(l, n)


test = int(input())
for i in range(0, test):
	a = [0 for x in range(0, 2001)]
	pair = 0
	size = int(input())
	arr = list(map(int, input().split(' ')))
	for j in range(0, size):
		a[arr[j] + 1000] = a[arr[j] + 1000] + 1
	for j in range(0, 2001):
		if a[j] != 0:
			pair = pair + int(a[j] * (a[j] - 1) / 2)
			if j < 1000:
				begin = 0
				end = 2 * j
			else:
				begin = 2 * j - 2000
				end = 2000
			while end != j and begin != j:
				pair = pair + a[end] * a[begin]
				end = end - 1
				begin = begin + 1
	print(int(pair))


def dictionary():
	dic = {}
	for i in range(-1000, 1001):
		dic[i] = 0
	return dic

def oddcount(odd_count, odd_list, d):
	c = 0
	for i in range(0, odd_count):
		num = d[odd_list[i]]
		c += num * (num - 1) // 2
		for j in range(i + 1, odd_count):
			if d[(odd_list[i] + odd_list[j]) // 2] >= 1:
				c += d[odd_list[i]] * d[odd_list[j]]
	return c

def evencount(even_count, even_list, d):
	c = 0
	for i in range(0, even_count):
		num = d[even_list[i]]
		c += num * (num - 1) // 2
		for j in range(i + 1, even_count):
			if d[(even_list[i] + even_list[j]) // 2] >= 1:
				c += d[even_list[i]] * d[even_list[j]]
	return c
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = dictionary()
	odd_list = []
	even_list = []
	odd_count = 0
	even_count = 0
	count = 0
	for i in range(n):
		if a[i] % 2 == 0:
			if d[a[i]] == 0:
				even_list += [a[i]]
				even_count += 1
		elif a[i] % 2 != 0:
			if d[a[i]] == 0:
				odd_list += [a[i]]
				odd_count += 1
		d[a[i]] += 1
	count += oddcount(odd_count, odd_list, d) + evencount(even_count, even_list, d)
	print(count)


t = int(input())
while t:
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [0] * 2001
	count = 0
	for x in a:
		b[x + 1000] += 1
	for i in range(0, 2000):
		if b[i] > 0:
			for j in range(i + 2, 2000, 2):
				if b[j] > 0:
					if b[int((i + j) / 2)] > 0:
						count += b[j] * b[i]
		if b[i] > 1:
			count += int(b[i] * (b[i] - 1) / 2)
	print(count)
	t -= 1


import itertools, sys
t = int(input().strip())

def pair(s, d):
	c = 0
	l = [thing for thing in itertools.combinations(d, 2)]
	for pair in l:
		i = pair[0]
		j = pair[1]
		if i + j in s:
			c += d[i] * d[j]
	for i in d:
		val = d[i]
		if val > 1:
			c += val * (val - 1) // 2
	return c
for case in range(t):
	n = int(input().strip())
	a = [int(i) for i in input().strip().split()]
	sd = set()
	do = {}
	de = {}
	for i in a:
		if i % 2 == 0:
			de[i] = de.get(i, 0) + 1
		else:
			do[i] = do.get(i, 0) + 1
		sd.add(2 * i)
	print(pair(sd, do) + pair(sd, de))


import math
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	ls = list(map(int, input().split(' ')))
	pro = [0] * 2001
	for i in range(n):
		pro[ls[i] + 1000] = pro[ls[i] + 1000] + 1
	result = 0
	for i in range(0, 2001, 1):
		if pro[i] > 1:
			result = result + int(pro[i] * (pro[i] - 1) / 2)
	for i in range(0, 2001, 1):
		for j in range(i + 2, 2001, 2):
			if pro[i] > 0 and pro[j] > 0 and (pro[int((i + j) / 2)] > 0):
				result = result + pro[i] * pro[j]
	print(result)


T = int(input())
for a0 in range(T):
	n = int(input())
	res = 0
	arr = list(map(int, input().split()))
	numbers = [0 for i in range(2001)]
	for i in range(n):
		numbers[arr[i] + 1000] += 1
	for i in range(2001):
		if numbers[i] == 0:
			continue
		res += numbers[i] * (numbers[i] - 1) // 2
		for j in range(i):
			if 2 * i - j > 2000:
				continue
			res += numbers[j] * numbers[2 * i - j]
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	count = []
	ans = 0
	for j in range(2001):
		count.append(0)
	for x in input().split():
		y = int(x)
		count[y + 1000] = count[y + 1000] + 1
	for j in range(2001):
		for k in range(j + 2, 2001, 2):
			if count[j] > 0 and count[k] > 0 and (count[(j + k) // 2] > 0):
				ans = ans + count[j] * count[k]
	for j in range(2001):
		ans = ans + count[j] * (count[j] - 1) // 2
	print(ans, end='\n')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = [0] * 2001
	cnt = 0
	for i in l:
		a[i + 1000] += 1
	for i in a:
		if i > 1:
			cnt += i * (i - 1) // 2
	cb = 0
	for i in range(2000):
		if a[i] != 0:
			x = i - 1000
			j = i + 2
			while j < 2001:
				if a[j] != 0:
					y = j - 1000
					z = (x + y) // 2
					if a[z + 1000] != 0:
						cb += a[i] * a[j]
				j += 2
	print(cnt + cb)


t = int(input())
while t > 0:
	n = int(input())
	c = [0 for i in range(-1000, 1001)]
	a = [int(x) for x in input().split()]
	for i in a:
		c[i + 1000] += 1
	cnt = 0
	for i in range(-1000, 1001):
		if c[i + 1000] == 0:
			continue
		(x, y) = (i, i)
		while x >= -1000 and y <= 1000:
			if x == y:
				cnt += int(c[x + 1000] * (c[x + 1000] - 1) / 2)
			else:
				cnt += c[x + 1000] * c[y + 1000]
			(x, y) = (x - 1, y + 1)
	print(cnt)
	t -= 1


from collections import Counter
from itertools import combinations
for q in range(int(input())):
	number = [{}, {}]
	s = {}
	ss = 0
	n = input()
	for i in map(int, input().split()):
		t = i % 2
		if i + i in s:
			number[t][i] += 1
		else:
			number[t][i] = 1
			s[i + i] = True
	for A in number:
		for x in combinations(A, 2):
			if sum(x) in s:
				ss += A[x[0]] * A[x[1]]
		for i in A:
			ss += A[i] * (A[i] - 1) // 2
	print(ss)


from itertools import combinations
for _ in range(int(input())):
	number = [{}, {}]
	loob = {}
	mid = 0
	n = input()
	for x in map(int, input().split()):
		t = x % 2
		if x + x in loob:
			number[t][x] += 1
		else:
			number[t][x] = 1
			loob[x * 2] = True
	for A in number:
		for x in combinations(A, 2):
			if sum(x) in loob:
				mid += A[x[0]] * A[x[1]]
		for d in A:
			mid += A[d] * (A[d] - 1) // 2
	print(mid)


from itertools import combinations
for i in range(int(input())):
	(N, A) = (int(input()), list(map(int, input().split())))
	(too, d) = ({}, [{}, {}])
	for i in A:
		t = i % 2
		if i in d[t]:
			d[t][i] += 1
		else:
			too[2 * i] = 0
			d[t][i] = 1
	mid = 0
	for even in d:
		for i in even:
			mid += (even[i] - 1) * even[i] // 2
		for (x, y) in combinations(even.keys(), r=2):
			if x + y in too:
				mid += even[x] * even[y]
	print(mid)


test = int(input())
while test > 0:
	test -= 1
	n = int(input())
	l = list(map(int, input().split()))
	a = [0] * 2001
	for x in l:
		a[x + 1000] += 1
	cou = 0
	for i in range(2001):
		if a[i] > 0:
			j = i
			while j <= 2000:
				if a[j] >= 1:
					if i == j:
						cou += a[i] * (a[i] - 1) // 2
					elif a[(i + j) // 2] > 0:
						cou += a[i] * a[j]
				j += 2
	print(cou)


from operator import mul
from fractions import Fraction
from functools import reduce

def nCk(n, k):
	return int(n * (n - 1) // 2)
t = int(input())
for z in range(t):
	n = int(input())
	line = input().split()
	elements = list(map(int, line))
	d = {}
	element_set = set(elements)
	final_set = set()
	for e in elements:
		try:
			d[e] += 1
		except KeyError:
			d[e] = 1
	elements = list(element_set)
	elements.sort()
	(even, odd) = ([], [])
	for x in elements:
		if x % 2 == 0:
			even.append(x)
		else:
			odd.append(x)
	count = 0
	for i in range(len(even)):
		for j in range(i + 1, len(even)):
			temp = (even[i] + even[j]) / 2
			if temp in element_set:
				count += d[even[i]] * d[even[j]]
		if d[even[i]] > 1:
			count += nCk(d[even[i]], 2)
	for i in range(len(odd)):
		for j in range(i + 1, len(odd)):
			temp = (odd[i] + odd[j]) / 2
			if temp in element_set:
				count += d[odd[i]] * d[odd[j]]
		if d[odd[i]] > 1:
			count += nCk(d[odd[i]], 2)
	print(count)


import math
t = int(input())
for _ in range(t):
	x = int(input())
	arr = list(map(int, input().split()))
	l = 2001
	n = l
	freq = [0] * l
	for i in range(len(arr)):
		freq[1001 + arr[i] - 1] += 1
	k = 0
	mid = n // 2
	count = 0
	for i in range(n):
		temp = 0
		mul = k
		if freq[i] > 0:
			temp += freq[i] * (freq[i] - 1) // 2
			while mul > 0:
				temp += freq[i - mul] * freq[i + mul]
				mul -= 1
		count += temp
		i += 1
		if n % 2 == 0:
			if i < mid:
				k += 1
			elif i > mid:
				k -= 1
		elif i <= mid:
			k += 1
		elif i >= mid:
			k -= 1
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	l = input().split()
	vals = [0] * 2001
	for i in l:
		vals[int(i) + 1000] += 1
	total = 0
	for i in range(2001):
		for j in range(i, 2001, 2):
			if i != j and vals[(i + j) // 2]:
				total += vals[i] * vals[j]
			elif i == j and vals[i] > 1:
				total += vals[i] * (vals[i] - 1) // 2
	print(total)


def give_me_count2(d):
	count = 0
	for (key, val) in d.items():
		count += val * (val - 1) // 2
	return count

def give_me_count(_dict, d):
	count = 0
	L = list(_dict.keys())
	for i in range(0, len(L) - 1):
		for j in range(i + 1, len(L)):
			if (L[i] + L[j]) // 2 in d:
				count += d[L[i]] * d[L[j]]
				pass
			pass
		pass
	return count

def take_input():
	N = int(input())
	L = map(int, input().split())
	d = {}
	(_even, _odd) = ({}, {})
	for i in L:
		d[i] = d.setdefault(i, 0) + 1
		if i % 2:
			_odd[i] = 1
		else:
			_even[i] = 1
	print(give_me_count2(d) + give_me_count(_even, d) + give_me_count(_odd, d))
T = int(input())
for i in range(T):
	take_input()


import itertools
import sys
import io

def mbc(n):
	return n + 1000

def mbdc(n):
	return n - 1000
for tests in range(int(input())):
	mb = [0] * 2000
	mb2 = [0] * 2000
	n = int(input())
	A = [int(i) for i in input().split()]
	for value in A:
		mb[mbc(value)] += 1
	for i in range(len(mb)):
		mb2[i] += mb[i] * (mb[i] - 1) // 2
		for j in range(i + 2, len(mb), 2):
			mb2[(i + j) // 2] += mb[i] * mb[j]
	print(sum([(i != 0) * j for (i, j) in zip(mb, mb2)]))


for t in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	R = set(A)
	(even, odd, pairs) = ([], [], 0)
	Occ = {}
	for x in A:
		if x not in Occ:
			Occ[x] = 1
		else:
			Occ[x] += 1
	for x in R:
		if x % 2 == 1:
			odd.append(x)
		else:
			even.append(x)
	for x in range(len(even)):
		occ = Occ[even[x]]
		if occ > 1:
			pairs += (occ - 1) * occ // 2
		if x == len(even) - 1:
			break
		for y in range(x + 1, len(even)):
			if (even[x] + even[y]) // 2 in R:
				pairs += occ * Occ[even[y]]
	for x in range(len(odd)):
		occ = Occ[odd[x]]
		if occ > 1:
			pairs += (occ - 1) * occ // 2
		if x == len(odd) - 1:
			break
		for y in range(x + 1, len(odd)):
			if (odd[x] + odd[y]) // 2 in R:
				pairs += occ * Occ[odd[y]]
	print(pairs)


def main():
	for _ in range(int(input())):
		n = int(input())
		count = 0
		indexing = [0 for x in range(2001)]
		array = [int(x) for x in input().split()]
		for i in array:
			indexing[i + 1000] += 1
		for i in range(2000):
			for j in range(i + 1, 2001):
				if indexing[i] > 0 and indexing[j] > 0:
					if (i + j) % 2 == 0:
						if indexing[(i + j) // 2] != 0:
							count += indexing[i] * indexing[j]
		for i in indexing:
			if i > 1:
				count += i * (i - 1) // 2
		print(count)
main()


T = int(input())
for i in range(T):
	N = int(input())
	array = list(map(int, input().split()))
	pairs = []
	total = 0
	for j in range(2001):
		pairs.append(0)
	for j in range(N):
		pairs[array[j] + 1000] += 1
	for j in range(-1000, 1001):
		index = j + 1000
		if pairs[index] == 0:
			continue
		else:
			if pairs[index] > 1:
				total += pairs[index] * (pairs[index] - 1) / 2
			for g in range(j + 2, 1001, 2):
				temp_index = g + 1000
				if pairs[temp_index] == 0:
					continue
				elif pairs[(j + g) // 2 + 1000] == 0:
					continue
				else:
					total += pairs[temp_index] * pairs[index]
	print(int(total))


import operator as op
from functools import reduce

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
T = int(input())
for i in range(T):
	N = int(input())
	A = [float(x) for x in input().split()]
	mymap = [0] * 2002
	maxv = 0
	myset = set(A)
	for x in A:
		if x > maxv:
			maxv = int(x)
		mymap[int(x) + 1000] += 1
	count = 0
	for k in myset:
		i = int(k) + 1000
		if mymap[i] == 0:
			continue
		for j in range(i + 2, 2002, 2):
			avg = (i + j) / 2
			if mymap[j] == 0:
				continue
			elif mymap[int(avg)] > 0:
				count += mymap[i] * mymap[j]
		if mymap[i] > 1:
			count += ncr(mymap[i], 2)
	print(count)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(set(a))
	fa = [0] * 2001
	ans = 0
	for j in a:
		fa[j + 1000] += 1
	for j in range(2001):
		for k in range(j + 2, 2001, 2):
			if fa[k] != 0:
				avg = (j + k) // 2
				if fa[avg] != 0:
					ans += fa[j] * fa[k]
		m = fa[j]
		ans += m * (m - 1) // 2
	print(ans)


counts = {}
sums = {}
for i in range(-2000, 2001):
	sums[i] = 0
	if i >= -1000 or i <= 1000:
		counts[i] = 0
t = int(input())
for y in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	counts = counts.fromkeys(counts, 0)
	sums = sums.fromkeys(sums, 0)
	odd = set()
	eve = set()
	eve_p = odd_p = 0
	for i in l:
		if counts[i]:
			if i % 2 == 0:
				eve.add(i)
			else:
				odd.add(i)
		elif i % 2 == 0:
			eve.add(i)
			eve_p += 1
		else:
			odd.add(i)
			odd_p += 1
		counts[i] += 1
		sums[2 * i] = 1
	odd = list(odd)
	eve = list(eve)
	count = 0
	if eve_p >= 2:
		for i in range(eve_p):
			count += counts[eve[i]] * (counts[eve[i]] - 1) // 2
			for j in range(i + 1, eve_p):
				if sums[eve[i] + eve[j]]:
					count += counts[eve[i]] * counts[eve[j]]
	elif eve_p == 1:
		count += counts[eve[0]] * (counts[eve[0]] - 1) // 2
	if odd_p >= 2:
		for i in range(odd_p):
			count += counts[odd[i]] * (counts[odd[i]] - 1) // 2
			for j in range(i + 1, odd_p):
				if sums[odd[i] + odd[j]]:
					count += counts[odd[i]] * counts[odd[j]]
	elif odd_p == 1:
		count += counts[odd[0]] * (counts[odd[0]] - 1) // 2
	print(count)


def fun(n):
	return n * (n - 1) // 2
for _ in range(int(input())):
	dic = dict.fromkeys([i for i in range(1000, -1001, -1)], 0)
	(odd, even, o, e) = ([], [], 0, 0)
	count = 0
	n = int(input())
	l = list(map(int, input().split()))
	for i in l:
		if i % 2 == 0 and (not dic[i]):
			even.append(i)
			e += 1
		elif not dic[i]:
			odd.append(i)
			o += 1
		dic[i] += 1
	for i in range(e):
		count += fun(dic[even[i]])
		for j in range(i + 1, e):
			temp = (even[i] + even[j]) // 2
			if dic[temp]:
				count += dic[even[i]] * dic[even[j]]
	for i in range(o):
		count += fun(dic[odd[i]])
		for j in range(i + 1, o):
			temp = (odd[i] + odd[j]) // 2
			if dic[temp]:
				count += dic[odd[i]] * dic[odd[j]]
	print(count)


t = int(input())
N = 2 * 10 ** 3 + 1
while t:
	n = int(input())
	a = list(map(int, input().split()))
	a = [i + 10 ** 3 for i in a]
	f = [0] * N
	for i in a:
		f[i] += 1
	c = 0
	for i in range(N):
		if f[i] != 0:
			for j in range(min(i, N - i - 1)):
				c += f[i - j - 1] * f[i + j + 1]
			c += f[i] * (f[i] - 1) // 2
	print(c)
	t -= 1


import itertools
testc = int(input())
for i in range(testc):
	even = []
	odd = []
	N = int(input())
	inputseq = input().split(' ')
	dict = {}
	for t in inputseq:
		t = int(t)
		if t in dict:
			dict[t] += 1
		else:
			dict[t] = 1
			if t % 2 == 0:
				even.append(t)
			else:
				odd.append(t)
	count = 0
	for pair in itertools.combinations(even, 2):
		avg = (pair[0] + pair[1]) / 2
		if avg in dict:
			count += dict[pair[0]] * dict[pair[1]]
	for pair in itertools.combinations(odd, 2):
		avg = (pair[0] + pair[1]) / 2
		if avg in dict:
			count += dict[pair[0]] * dict[pair[1]]
	for i in dict:
		if dict[i] > 1:
			count += dict[i] * (dict[i] - 1) // 2
	print(count)


test = int(input())
for i in range(test):
	N = int(input())
	arr = list(map(int, input().split()))
	s = set(arr)
	arr.sort()
	d = dict()
	for i in arr:
		d[i] = d.get(i, 0) + 1
	flag = 0
	for i in d.keys():
		if d[i] >= 2:
			flag += d[i] * (d[i] - 1) // 2
	even_arr = []
	odd_arr = []
	(n, m) = (0, 0)
	for i in d.keys():
		if i % 2 == 0:
			even_arr.append(i)
			n += 1
		else:
			odd_arr.append(i)
			m += 1
	count = 0
	for i in range(n - 1):
		for j in range(n - 1, i, -1):
			avg = (even_arr[i] + even_arr[j]) // 2
			if avg in s:
				count += d[even_arr[i]] * d[even_arr[j]]
	for i in range(m - 1):
		for j in range(m - 1, i, -1):
			avg = (odd_arr[i] + odd_arr[j]) // 2
			if avg in s:
				count += d[odd_arr[i]] * d[odd_arr[j]]
	print(flag + count)


for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	aset = set(a)
	r = 0
	d = dict()
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	while d:
		(v1, n1) = d.popitem()
		if n1 > 1:
			r += n1 * (n1 - 1) // 2
		for v2 in d:
			if (v1 + v2) / 2 in aset:
				n2 = d[v2]
				r += n1 * n2
	print(r)


import itertools
test_cases = int(input())
for i in range(test_cases):
	L_even = []
	L_odd = []
	N = int(input())
	sequence = input().split(' ')
	seq_dict = {}
	for n in sequence:
		n = int(n)
		if n in seq_dict:
			seq_dict[n] += 1
		else:
			seq_dict[n] = 1
			if n % 2 == 0:
				L_even.append(n)
			else:
				L_odd.append(n)
	count = 0
	for pair in itertools.combinations(L_even, 2):
		temp = (pair[0] + pair[1]) / 2
		if temp in seq_dict:
			count += seq_dict[pair[0]] * seq_dict[pair[1]]
	for pair in itertools.combinations(L_odd, 2):
		temp = (pair[0] + pair[1]) / 2
		if temp in seq_dict:
			count += seq_dict[pair[0]] * seq_dict[pair[1]]
	for n in seq_dict:
		if seq_dict[n] > 1:
			count += seq_dict[n] * (seq_dict[n] - 1) // 2
	print(count)


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	cts = [0] * 2001
	for num in nums:
		cts[num + 1000] += 1
	ct = 0
	for i in range(2001):
		if cts[i] > 0:
			ct += cts[i] * (cts[i] - 1) // 2
			for j in range(i + 2, 2001, 2):
				if cts[(i + j) // 2] > 0 and cts[j] > 0:
					ct += cts[i] * cts[j]
	print(ct)


t = input()
for i in range(int(t)):
	s = 0
	n = input()
	n = int(n)
	arr = list(map(int, input().split()))
	e = []
	o = []
	a = {}
	k = 0
	for i in range(n):
		if arr[i] % 2 == 0:
			e.append(arr[i])
		else:
			o.append(arr[i])
	for i in arr:
		try:
			a[i] = a[i] + 1
		except:
			a[i] = 1
	o = set(o)
	e = set(e)
	o = list(o)
	e = list(e)
	c = []
	for i in range(len(o)):
		try:
			h = a[o[i]]
			s = s + int(h * (h - 1) / 2)
		except:
			s += 0
		for j in range(i + 1, len(o)):
			avg = (o[i] + o[j]) / 2
			try:
				if a[avg]:
					k += a[o[i]] * a[o[j]]
			except:
				k += 0
	for i in range(len(e)):
		try:
			h = a[e[i]]
			s = s + h * (h - 1) / 2
		except:
			s += 0
		for j in range(i + 1, len(e)):
			avg = (e[i] + e[j]) / 2
			try:
				if a[avg]:
					k += a[e[i]] * a[e[j]]
			except:
				k += 0
	x = s + k
	x = int(x)
	print(x)


t = int(input())
for i in range(t):
	c = 0
	n = int(input())
	a = []
	a = [0 for x in range(2001)]
	j = input().split(' ')
	for x in j:
		a[int(x) + 1000] += 1
	for u in range(2001):
		if a[u] == 0:
			continue
		for k in range((2000 - u) // 2 + 1):
			if k == 0:
				c += a[u] * (a[u] - 1) / 2
			elif a[u + k]:
				c += a[u] * a[u + 2 * k]
	print(int(c))


T = int(input())
for t in range(T):
	count = 0
	N = int(input())
	A = [int(x) for x in input().split()]
	f = [0] * 2001
	for i in range(N):
		f[A[i] + 1000] += 1
	for i in range(-1000, 999):
		if f[i + 1000] == 0:
			continue
		for m in range(i + 1, 1000):
			j = 2 * m - i
			if j > 1000:
				break
			if f[m + 1000] > 0 and f[j + 1000] > 0:
				count += f[j + 1000] * f[i + 1000]
	for i in range(2001):
		count += f[i] * (f[i] - 1) // 2
	print(count)


def AvgPairs(sequence):
	Corr = [0 for i in range(2001)]
	for i in sequence:
		Corr[1000 + i] += 1
	count = 0
	for i in range(0, 2001):
		if Corr[i] > 1:
			count += Corr[i] * (Corr[i] - 1) // 2
		if 0 < i < 2000 and Corr[i] > 0:
			low = i - 1
			high = i + 1
			while low >= 0 and high <= 2000:
				if Corr[low] > 0 and Corr[high] > 0:
					count += Corr[low] * Corr[high]
				low -= 1
				high += 1
	print(count)
T = int(input())
for i in range(T):
	n = int(input())
	sequence = list(map(int, input().split()))
	AvgPairs(sequence)


t1 = int(input())
for x in range(t1):
	check = [[False, 0] for x in range(2001)]
	count = 0
	n = int(input())
	e = [int(y) for y in input().split()]
	for y in e:
		check[y][0] = True
		check[y][1] += 1
	for t in range(-999, 998, 2):
		if not check[t][0]:
			continue
		f = check[t][1]
		count += int(f * (f - 1) / 2)
		for r in range(t + 2, 1000, 2):
			if not check[r][0]:
				continue
			s = check[r][1]
			d = t + r
			d >>= 1
			if check[d][0]:
				count += s * f
	for t in range(-1000, 999, 2):
		if not check[t][0]:
			continue
		f = check[t][1]
		count += int(f * (f - 1) / 2)
		for r in range(t + 2, 1001, 2):
			if not check[r][0]:
				continue
			s = check[r][1]
			d = t + r
			d >>= 1
			if check[d][0]:
				count += s * f
	print(count)


t = int(input())
for l in range(0, t, 1):
	n = int(input())
	h = []
	for i in range(0, 2001):
		h.append(0)
	ans = 0
	j = input().split(' ')
	for i in j:
		k = int(i)
		k += 1000
		h[k] += 1
	for i in range(2001):
		j = min(i, 2000 - i)
		if h[i] > 0:
			for k in range(1, j + 1):
				ans += h[i - k] * h[i + k]
		ans += h[i] * (h[i] - 1) // 2
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	aa = []
	for i in range(n):
		aa.append(0)
		aa[i] = a[i] * 2
	aa = set(aa)
	count = 0
	odd = []
	e = []
	od = {}
	oe = {}
	ds = []
	es = []
	for i in range(n):
		if a[i] % 2 == 0:
			e.append(a[i])
			if a[i] not in oe:
				oe[a[i]] = 1
			else:
				oe[a[i]] = oe[a[i]] + 1
		else:
			odd.append(a[i])
			if a[i] not in od:
				od[a[i]] = 1
			else:
				od[a[i]] = od[a[i]] + 1
	ds = set(odd)
	es = set(e)
	ds = list(ds)
	es = list(es)
	for i in range(len(ds)):
		y = od[ds[i]]
		if y > 1:
			count += y * (y - 1) // 2
	for i in range(len(ds) - 1):
		for j in range(i + 1, len(ds)):
			x = ds[i] + ds[j]
			if x in aa:
				count += od[ds[i]] * od[ds[j]]
	for i in range(len(es)):
		y = oe[es[i]]
		if y > 1:
			count += y * (y - 1) // 2
	for i in range(len(es) - 1):
		for j in range(i + 1, len(es)):
			x = es[i] + es[j]
			if x in aa:
				count += oe[es[i]] * oe[es[j]]
	print(count)
	t -= 1


t = input()
t = int(t)
for a0 in range(1, t + 1):
	n = input()
	n = int(n)
	a = list(map(int, input().split()))
	b = {}
	even = []
	odd = []
	for i in range(-1001, 1002):
		b[i] = 0
	for i in a:
		b[i] += 1
	for i in set(a):
		if i % 2 == 0:
			even.append(i)
		elif i % 2 != 0:
			odd.append(i)
	ct = 0
	for i in range(-1001, 1002):
		ct += b[i] * (b[i] - 1) // 2
	for i in range(0, len(even) - 1):
		for j in range(i + 1, len(even)):
			if b[(even[i] + even[j]) // 2] > 0:
				ct += 1 * b[even[i]] * b[even[j]]
	for i in range(0, len(odd) - 1):
		for j in range(i + 1, len(odd)):
			if b[(odd[i] + odd[j]) // 2] > 0:
				ct += 1 * b[odd[i]] * b[odd[j]]
	print(ct)


tc = int(input())
for tt in range(tc):
	n = int(input())
	a = [int(x) + 1005 for x in input().split()]
	haso = [0 for i in range(2100)]
	for x in a:
		haso[x] += 1
	count = 0
	for i in range(1, 2100):
		if haso[i] > 0:
			count += haso[i] * (haso[i] - 1) // 2
			for j in range(i + 2, 2100, 2):
				if haso[j] > 0 and haso[(i + j) // 2] > 0:
					count += haso[i] * haso[j]
	print(count)


for t in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	cnt = [0 for _ in range(2001)]
	for a in A:
		cnt[1000 + a] += 1
	ans = 0
	for pos in range(2001):
		if cnt[pos] > 0:
			ans += cnt[pos] * (cnt[pos] - 1) // 2
			for d in range(1, min(2000 - pos, pos) + 1):
				ans += cnt[pos - d] * cnt[pos + d]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	s = list(set(a))
	s.sort()
	m = len(s)
	l = [0] * m
	l[0] = 1
	j = 0
	for i in range(1, n):
		if a[i] == s[j]:
			l[j] += 1
		else:
			j += 1
			l[j] += 1
	b = [0] * 100005
	ans = 0
	o = []
	e = []
	ol = []
	el = []
	for i in range(m):
		b[s[i]] = 1
		if s[i] % 2 == 0:
			e.append(s[i])
			el.append(l[i])
		else:
			o.append(s[i])
			ol.append(l[i])
	if len(e) != 0:
		for i in range(len(e) - 1):
			for j in range(i + 1, len(e)):
				m = (e[i] + e[j]) // 2
				if b[m] == 1:
					ans += el[i] * el[j]
			if el[i] > 1:
				p = el[i]
				ans += p * (p - 1) // 2
	if len(e) != 0:
		if el[-1] > 1:
			p = el[-1]
			ans += p * (p - 1) // 2
	if len(o) != 0:
		for i in range(len(o) - 1):
			for j in range(i + 1, len(o)):
				m = (o[i] + o[j]) // 2
				if b[m] == 1:
					ans += ol[i] * ol[j]
			if ol[i] > 1:
				p = ol[i]
				ans += p * (p - 1) // 2
	if len(o) != 0:
		if ol[-1] > 1:
			p = ol[-1]
			ans += p * (p - 1) // 2
	print(ans)


for a in range(int(input())):
	n = int(input())
	c = 0
	d = {}
	l = [int(e) for e in input().split()]
	o = []
	e = []
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for i in d:
		if d[i] > 1:
			c += int((d[i] - 1) * d[i] / 2)
		if i % 2 == 0:
			e.append(i)
		else:
			o.append(i)
	for i in range(len(e) - 1):
		for j in range(i + 1, len(e)):
			if (e[i] + e[j]) / 2 in d:
				c += d[e[j]] * d[e[i]]
	for i in range(len(o) - 1):
		for j in range(i + 1, len(o)):
			if (o[i] + o[j]) / 2 in d:
				c += d[o[j]] * d[o[i]]
	print(c)


def nCr(n, r):
	s = n * (n - 1)
	s = int(s / 2)
	return s
t = int(input())
for iss in range(t):
	c = 0
	nn = int(input())
	a = [int(x) for x in input().split()]
	ma = max(a)
	mi = min(a)
	maa = max(abs(ma), abs(mi))
	n = maa
	d = {}
	for i in range(-1 * n, n + 1):
		d[i] = 0
	for i in a:
		d[i] += 1
	for i in range(n, -1, -1):
		pp = n - i
		if d[i] > 0:
			for j in range(pp + 1):
				if j == 0:
					if d[i] > 1:
						c += int(nCr(d[i], 2))
				elif d[i + j] > 0:
					if d[i - j] > 0:
						c += d[i + j] * d[i - j]
	for i in range(-n, 0):
		pp = abs(-n - i)
		if d[i] > 0:
			for j in range(pp + 1):
				if j == 0:
					if d[i] > 1:
						c += int(nCr(d[i], 2))
				elif d[i + j] > 0:
					if d[i - j] > 0:
						c += d[i - j] * d[i + j]
	print(c)


def Triangular(n):
	return n * (n + 1) // 2
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	numberFrequencies = [0 for i in range(-1000, 1001)]
	for a in A:
		numberFrequencies[a + 1000] += 1
	pairsFound = 0
	for v in numberFrequencies:
		if v >= 2:
			pairsFound += Triangular(v - 1)
	for i in range(-1000, 1000):
		if numberFrequencies[i + 1000] == 0:
			continue
		for j in range(i + 2, 1000, 2):
			if numberFrequencies[j + 1000] == 0:
				continue
			midpoint = (i + j) // 2
			if numberFrequencies[midpoint + 1000] == 0:
				continue
			pairsFound += numberFrequencies[i + 1000] * numberFrequencies[j + 1000]
	print(pairsFound)


from collections import Counter
from itertools import islice
t = int(input())
for _ in range(t):
	input()
	a = Counter(map(int, input().split()))
	v = ([], [])
	for x in a.items():
		v[x[0] & 1].append(x)
	c = sum((x * (x - 1) // 2 + sum((x * y for (lj, y) in islice(l, i) if (li + lj) // 2 in a)) for l in v for (i, (li, x)) in enumerate(l)))
	print(c)


t = int(input())
for i in range(t):
	count = 0
	d = dict()
	odd = list()
	even = list()
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(n):
		if 2 * l[i] in d:
			d[2 * l[i]] += 1
		else:
			d[2 * l[i]] = 1
	k = list(set(l))
	for i in range(len(k)):
		if k[i] % 2 == 0:
			even.append(k[i])
		else:
			odd.append(k[i])
		if d[2 * k[i]] >= 2:
			count += d[2 * k[i]] * (d[2 * k[i]] - 1) // 2
	for i in range(len(even)):
		for j in range(i + 1, len(even)):
			if even[i] + even[j] in d:
				count += d[2 * even[i]] * d[2 * even[j]]
	for i in range(len(odd)):
		for j in range(i + 1, len(odd)):
			if odd[i] + odd[j] in d:
				count += d[2 * odd[i]] * d[2 * odd[j]]
	print(count)


from collections import Counter
from itertools import islice
t = int(input())
for _ in range(t):
	input()
	a = Counter(map(int, input().split()))
	odd = [x for x in a if x & 1]
	even = [x for x in a if not x & 1]
	c = 0
	for l in (odd, even):
		for (i, li) in enumerate(l):
			x = a[li]
			c += x * (x - 1) // 2
			for (j, lj) in enumerate(islice(l, i)):
				if (li + lj) // 2 in a:
					c += x * a[lj]
	print(c)