You are given an array $a$ consisting of $n$ integers.

Let's call a pair of indices $i$, $j$ good if $1 \le i < j \le n$ and $\gcd(a_i, 2a_j) > 1$ (where $\gcd(x, y)$ is the greatest common divisor of $x$ and $y$).

Find the maximum number of good index pairs if you can reorder the array $a$ in an arbitrary way.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of the test case contains a single integer $n$ ($2 \le n \le 2000$) — the number of elements in the array.

The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.


-----Output-----

For each test case, output a single integer — the maximum number of good index pairs if you can reorder the array $a$ in an arbitrary way.


-----Examples-----

Input
3
4
3 6 5 3
2
1 7
5
1 4 2 4 1
Output
4
0
9


-----Note-----

In the first example, the array elements can be rearranged as follows: $[6, 3, 5, 3]$.

In the third example, the array elements can be rearranged as follows: $[4, 4, 2, 1, 1]$.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Greedy algorithms

Complete search

Number theory

Mathematics


Solutions:
from math import gcd
for _ in range(int(input())):
	res = 0
	n = int(input())
	nums = []
	one = 0
	even = 0
	for i in input().split():
		i = int(i)
		if i == 0:
			continue
		if i == 1:
			one += 1
		elif i % 2 == 0:
			even += 1
		else:
			nums.append(i)
	n = len(nums)
	res += one * even
	del one
	res += even * n
	res += sum(range(even))
	if len(nums) > 1:
		while nums:
			num = nums.pop()
			res += len([1 for i in nums if gcd(num, i) > 1])
	print(res)


def ff(m):
	d = 3
	r = set()
	dd = round(pow(m, 0.5)) + 1
	while m - 1 and d < dd:
		if m % d == 0:
			r.add(d)
			m = m // d
			dd = round(pow(m, 0.5)) + 1
		else:
			d += 2
	if m != 1:
		r.add(m)
	return r
for _ in range(int(input())):
	res = 0
	n = int(input())
	nums = []
	one = 0
	even = 0
	for i in input().split():
		i = int(i)
		if i == 0:
			continue
		if i == 1:
			one += 1
		elif i % 2 == 0:
			even += 1
		else:
			nums.append(ff(i))
	n = len(nums)
	res += one * even
	del one
	res += even * n
	res += sum(range(even))
	if len(nums) > 1:
		while nums:
			num = nums.pop()
			res += sum([1 for i in nums if num & i])
	print(res)


from collections import Counter
from itertools import accumulate, product, groupby
import operator
import math
from functools import reduce

def solve():
	n = int(input())
	arr = [int(char) for char in input().split()]
	(even, odd) = ([], [])
	for a in arr:
		if a & 1:
			odd.append(a)
		else:
			even.append(a)
	(E, O) = (len(even), len(odd))
	ans = 0
	for j in range(1, E + 1):
		ans += n - j
	for (i, num) in enumerate(odd):
		for j in range(i + 1, O):
			if math.gcd(num, odd[j]) > 1:
				ans += 1
	return ans
for _ in range(int(input())):
	print(solve())


from math import gcd
for test_case in range(int(input())):
	n = int(input())
	l = sorted(map(int, input().split()), key=lambda x: x & 1)
	print(sum((len([x for x in l[i + 1:] if gcd(l[i], 2 * x) > 1]) for i in range(n))))


from math import gcd

def check(l2, p):
	sum1 = 0
	for j in l2:
		if gcd(p, 2 * j) > 1:
			sum1 += 1
	return sum1
for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = []
	l3 = []
	for i in l1:
		if i % 2 == 0:
			l2.append(i)
		else:
			l3.append(i)
	l1 = l2 + l3
	count = 0
	for i in range(n):
		if l1[i] % 2 == 0:
			count += len(l1[i + 1:])
		else:
			p = check(l1[i + 1:], l1[i])
			count += p
	print(count)


import math
t = int(input())
while t:
	t -= 1
	n = int(input())
	lis = []
	ans = 0
	for i in map(int, input().split()):
		if i & 1:
			for j in lis:
				if math.gcd(i, j) > 1:
					ans += 1
			lis.append(i)
	print(ans + len(lis) * (n - len(lis)) + (n - len(lis) - 1) * (n - len(lis)) // 2)


from math import gcd

def main():
	ans = ''
	for _ in range(int(input())):
		n = int(input())
		nums = list(map(int, input().split()))
		how_many_even = 0
		max_good_index_pair = 0
		for (index, value) in enumerate(nums):
			if value % 2 == 0:
				max_good_index_pair += n - 1 - how_many_even
				how_many_even += 1
			else:
				for (index2, value2) in enumerate(nums[index + 1:], start=index + 1):
					if value2 % 2 != 0 and gcd(value, value2) != 1:
						max_good_index_pair += 1
		ans += f'{max_good_index_pair}\n'
	print(ans)
main()


import math
for s in [*open(0)][2::2]:
	a = sorted(map(int, s.split()), key=lambda x: x % 2)
	print(sum((math.gcd(2 * x, y) > 1 for (i, x) in enumerate(a) for y in a[:i])))


import math
for Input in [*open(0)][2::2]:
	L = sorted(map(int, Input.split()), key=lambda x: x % 2)
	print(sum((1 < math.gcd(2 * x, y) for (i, x) in enumerate(L) for y in L[:i])))


import math
f = lambda x: x % 2
for s in [*open(0)][2::2]:
	a = sorted(map(int, s.split()), key=f)
	n = len(a)
	k = n - sum(map(f, a))
	b = a[k:]
	print(k * (2 * n - k - 1) // 2 + sum((math.gcd(x, y) > 1 for (i, x) in enumerate(b) for y in b[:i])))


import math as m

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		ns = list(map(int, input().split(' ')))
		ns.sort(key=lambda x: x % 2)
		good = 0
		for i in range(n - 1):
			if ns[i] % 2 == 0:
				good += n - i - 1
			else:
				good += sum((m.gcd(ns[i], ns[j]) > 1 for j in range(i + 1, n)))
		print(good)
main()


from math import gcd

def print_sol(c, sol):
	print('Case #{}: {}'.format(c, sol))

def rd_int():
	return int(input())

def rd_str():
	return input()

def rd_str_lst():
	return input().split(' ')

def sp_str_lst():
	return list(input())

def rd_int_lst():
	return [int(i) for i in rd_str_lst()]

def sp_int_lst():
	return [int(i) for i in sp_str_lst()]

def main():
	t = rd_int()
	for c in range(1, t + 1):
		n = rd_int()
		a = rd_int_lst()
		even_count = 0
		odd_numbers = []
		for i in range(n):
			if a[i] % 2 == 0:
				even_count += 1
			elif a[i] > 1:
				odd_numbers.append(a[i])
		ans = even_count / 2 * (2 * n - 1 - even_count)
		for i in range(len(odd_numbers)):
			for j in range(i + 1, len(odd_numbers)):
				if gcd(odd_numbers[i], odd_numbers[j]) > 1:
					ans += 1
		print(int(ans))
main()


import math
import itertools
t = int(input())
for _ in range(t):
	n = int(input())
	arr = tuple(map(int, input().split()))
	even = sum((1 for i in arr if i % 2 == 0))
	pairs_from_even = 0
	for i in range(1, even + 1):
		pairs_from_even += n - i
	odd = (i for i in arr if i % 2 == 1)
	pairs_from_odd = 0
	for (a, b) in itertools.combinations(odd, 2):
		if math.gcd(a, b) > 1:
			pairs_from_odd += 1
	print(pairs_from_even + pairs_from_odd)


import sys
from os import path
import math
import time
from collections import defaultdict
from sys import setrecursionlimit
setrecursionlimit(10 ** 8)
MOD = 10 ** 9 + 7
INT_MAX = 10 ** 9
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def test_case():
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = list(map(int, input().split()))
		count = 0
		even = 0
		odd = []
		for i in range(n):
			if s[i] % 2 == 0:
				even += 1
			else:
				odd.append(s[i])
		if even >= 1:
			count = even * (even - 1) / 2 + even * len(odd)
		for i in range(len(odd) - 1):
			for j in range(i + 1, len(odd)):
				if math.gcd(odd[i], odd[j]) > 1:
					count += 1
		print(int(count))
test_case()


import sys
input = sys.stdin.readline

def print(x, end='\n'):
	sys.stdout.write(str(x) + end)

def get_int():
	return int(input())

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

def get_char_list():
	s = input()
	return list(s[:len(s) - 1])

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

def print_iterable(p):
	print(' '.join(map(str, p)))
from math import gcd

def main():
	t = get_int()
	for i in range(t):
		n = get_int()
		a = get_list_ints()
		temp = 0
		c = 0
		count = 0
		for j in range(n):
			if a[j] % 2 == 0:
				temp = a[j]
				a[j] = a[c]
				a[c] = temp
				c += 1
		s = 0
		for j in range(n):
			for k in range(j + 1, n):
				if gcd(a[j], a[k] * 2) > 1:
					s += 1
		print(s)
main()


from math import gcd

def cal(n, a):
	b = 0
	a.sort(reverse=True)
	l1 = []
	l2 = []
	for i in range(len(a)):
		if a[i] % 2 == 0:
			l2.append(a[i])
		else:
			l1.append(a[i])
	l2.extend(l1)
	for i in range(n):
		for j in range(i + 1, n):
			if gcd(l2[i], l2[j] * 2) > 1:
				b += 1
	print(b)
t = int(input())
l1 = []
l2 = []
for i in range(t):
	n = int(input())
	l1.append(n)
	a = list(map(int, input().split()))
	l2.append(a)
for i in range(len(l1)):
	cal(l1[i], l2[i])


import math

def gcd1(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def sol(n, arr):
	oddarr = []
	e = 0
	for i in range(0, n):
		if arr[i] % 2 == 0:
			e += 1
		else:
			oddarr.append(arr[i])
	result = n * (n - 1) // 2 - (n - e) * (n - e - 1) // 2
	ans = 0
	for i in range(0, len(oddarr)):
		for j in range(i + 1, len(oddarr)):
			if math.gcd(oddarr[i], oddarr[j]) > 1:
				ans += 1
	print(result + ans)
t = int(input())
for i in range(0, t):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	sol(n, arr)


def solve():
	n = int(input())
	vsi = list(map(int, input().split()))
	vsi.sort(key=lambda x: x % 2 == 0, reverse=True)
	import math
	o = 0
	for (i, x) in enumerate(vsi):
		for y in vsi[i + 1:]:
			if math.gcd(x, 2 * y) > 1:
				o += 1
	return o
t = int(input())
for x in range(t):
	print(solve())


from math import gcd

def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	b = sorted(a, key=lambda x: x % 2)
	cnt = 0
	for i in range(n):
		for j in range(i + 1, n):
			cnt += gcd(b[i], 2 * b[j]) > 1
	print(cnt)
t = int(input())
for _ in range(t):
	solve()


import math as m
for x in range(int(input())):
	n = int(input())
	arr = input().split()
	(aro, are) = ([], [])
	ans = 0
	for x in arr:
		if int(x) % 2:
			aro.append(int(x))
		else:
			are.append(int(x))
	for x in range(len(aro) - 1):
		for y in aro[x + 1:]:
			ans += m.gcd(aro[x], y) > 1
	(n, n1) = (len(arr), len(aro))
	ans += n * (n - 1) // 2 - n1 * (n1 - 1) // 2
	print(ans)


from math import gcd
t = int(input())
for _ in range(t):
	n = int(input())
	s = 0
	a = [int(x) for x in input().split()]
	(p, b) = ([x for x in a if x % 2], [x for x in a if x % 2 == 0])
	for (i, x) in enumerate(p):
		for j in range(i + 1, len(p)):
			if gcd(x, p[j]) > 1:
				s += 1
	print(s + len(b) * len(p) + len(b) * (len(b) - 1) // 2)


from math import gcd
for _ in range(0, int(input())):
	n = int(input())
	v = map(int, input().split())
	o = []
	e = 0
	for x in v:
		if x % 2 == 0:
			e += 1
		else:
			o.append(x)
	o = sorted(o)
	a = sum((i - 1 for i in range(n, n - e, -1)))
	for x in range(0, len(o) - 1):
		if o[x] == 1:
			continue
		for y in range(x + 1, len(o)):
			if gcd(o[y], o[x]) > 2:
				a += 1
	print(a)


from math import gcd

def fun(ls, n):
	even = []
	rest = []
	for i in ls:
		if i % 2 == 0:
			even.append(i)
		else:
			rest.append(i)
	lt = even + rest
	count = 0
	for i in range(n):
		for j in range(i + 1, n):
			if gcd(lt[i], 2 * lt[j]) > 1:
				count += 1
	print(count)
T = int(input())
for i in range(T):
	n = int(input())
	ls = list(map(int, input().split()))
	fun(ls, n)


import math

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	sor = []
	for x in arr:
		if x % 2 == 0:
			sor.append(x)
	for x in arr:
		if x % 2 != 0:
			sor.append(x)
	ans = 0
	for i in range(n):
		for j in range(i + 1, n):
			if math.gcd(sor[i], 2 * sor[j]) > 1:
				ans += 1
	print(ans)
t = int(input())
for _ in range(t):
	solve()


from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	par = 0
	impar = list()
	res = 0
	for i in a:
		if i % 2 == 0:
			par += 1
		elif i == 1:
			continue
		else:
			impar.append(i)
	for i in range(par):
		res += n - i - 1
	for i in range(len(impar)):
		for j in range(i + 1, len(impar)):
			if gcd(impar[i], impar[j]) > 1:
				res += 1
	print(res)


from math import gcd
for i in range(int(input())):
	e = int(input())
	nums = list(map(int, input().split()))
	numsorted = []
	for i in range(e):
		if nums[i] % 2 == 0:
			numsorted.append(nums[i])
	numsorted.sort()
	for i in range(e):
		if nums[i] % 2 != 0:
			numsorted.append(nums[i])
	count = 0
	for i in range(e):
		for j in numsorted[i + 1:]:
			if gcd(numsorted[i], j * 2) > 1:
				count += 1
	print(count)


import math

def main():
	t = int(input())
	for _ in range(t):
		print(case())

def case():
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	odds = []
	for num in a:
		if num % 2:
			odds.append(num)
		else:
			b.append(num)
	return count_pair(b + odds)

def count_pair(a):
	count = 0
	for i in range(len(a)):
		for j in range(i + 1, len(a)):
			if math.gcd(a[i], a[j] * 2) > 1:
				count += 1
	return count

def is_gcd(a, b):
	for i in range(2, min(a, b) + 1):
		if a % i == 0 and b % i == 0:
			return True
	return False
main()


import sys
from math import gcd
input = sys.stdin.readline

def solve():
	n = int(input())
	a = []
	b = []
	for v in map(int, input().split()):
		if v % 2 == 0:
			a.append(v)
		else:
			b.append(v)
	a += b
	r = 0
	for i in range(n):
		for j in range(i):
			r += gcd(a[j], 2 * a[i]) > 1
	print(r)
for i in range(int(input())):
	solve()


import math

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	answer = 0
	for i in range(n):
		if a[i] % 2 == 0:
			b.insert(0, a[i])
		else:
			b.append(a[i])
	for i in range(n):
		if b[i] % 2 == 0:
			answer += n - i - 1
		else:
			for j in range(i + 1, n):
				if math.gcd(b[i], 2 * b[j]) > 1:
					answer += 1
	return answer
t = int(input())
while t > 0:
	t -= 1
	print(solve())


import math

def solve(N, A):
	even = list(filter(lambda a: a & 1 == 0, A))
	odd = list(filter(lambda a: a & 1 == 1, A))
	even.sort()
	odd.sort()
	SA = even + odd
	cnt = 0
	for i in range(N - 1):
		for j in range(i + 1, N):
			if math.gcd(SA[i], 2 * SA[j]) > 1:
				cnt += 1
	print(cnt)
T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	solve(N, A)


import math
t = int(input())
p = []
for _ in range(t):
	n = int(input())
	a = sorted([int(x) for x in input().split()], key=lambda x: (1 - (x & 1), x))
	ret = 0
	for i in range(n - 1):
		ati = a[i] << 1
		for j in range(i + 1, n):
			if math.gcd(ati, a[j]) > 1:
				ret += 1
	p.append(ret)
for x in p:
	print(x)


from math import gcd
for _ in range(int(input())):
	count = 0
	n = int(input())
	l = [int(x) for x in input().split()]
	u = list()
	(e, o) = (0, 0)
	for x in l:
		if x % 2 == 0:
			e = e + 1
			u.insert(0, x)
		else:
			o = o + 1
			u.append(x)
	for i in range(e, n):
		for j in range(i + 1, n):
			if gcd(u[i], u[j]) > 1:
				count = count + 1
	count = count + o * e + int(e * (e - 1) / 2)
	print(count)


from math import gcd
res = ''
for _ in range(int(input())):
	n = int(input())
	arr = tuple(map(int, input().split()))
	new_arr = [0] * n
	(l, r) = (0, n - 1)
	even = odd = 0
	for i in arr:
		if i % 2 == 0:
			new_arr[l] = i
			l += 1
			even += 1
		else:
			new_arr[r] = i
			r -= 1
			odd += 1
	ans = 0
	while even > 0:
		ans += even - 1 + odd
		even -= 1
	for i in range(r + 1, n - 1):
		for j in range(i + 1, n):
			ans += gcd(new_arr[i], new_arr[j]) > 1
	res += str(ans) + '\n'
print(res)


a = int(input())
from math import gcd
for i in range(a):
	e = 0
	f = []
	b = int(input())
	c = input().split()
	d = [int(i) for i in c]
	for j in d:
		if j % 2 == 0:
			e += 1
		else:
			f.append(j)
	l = 0
	for k in range(b - e - 1):
		for h in range(k + 1, b - e, 1):
			if gcd(f[k], f[h]) != 1:
				l += 1
	print(int((b - e) * e + e * (e - 1) / 2 + l))


import sys
from math import *
input = lambda : sys.stdin.readline()
int_arr = lambda : list(map(int, input().split()))
str_arr = lambda : list(map(str, input().split()))
get_str = lambda : map(str, input().split())
get_int = lambda : map(int, input().split())
get_flo = lambda : map(float, input().split())

def solve(n, arr):
	(odd, even) = ([], [])
	for i in range(n):
		if arr[i] % 2 == 0:
			even.append(arr[i])
		else:
			odd.append(arr[i])
	arr = sorted(even)[::-1] + sorted(odd)[::-1]
	c = 0
	for i in range(n):
		for j in range(i + 1, n):
			if gcd(arr[i], 2 * arr[j]) > 1:
				c += 1
	print(c)
for _ in range(int(input())):
	n = int(input())
	arr = int_arr()
	solve(n, arr)


from math import gcd

def is_prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(n ** 0.5) + 1
	for divisor in range(3, sqr, 2):
		if n % divisor == 0:
			return False
	return True
cases = int(input())
for case in range(0, cases):
	n = int(input())
	array = [int(x) for x in input().split(' ')]
	one_count = 0
	prime_count = 0
	even_count = 0
	odd_count = 0
	odd_array = []
	for num in array:
		if num == 1:
			one_count += 1
		elif num % 2 == 0:
			even_count += 1
		elif num % 2 != 0:
			odd_count += 1
			odd_array.append(num)
	result = 0
	for i in range(0, even_count):
		result += n - i - 1
	odd_array = sorted(odd_array, reverse=True)
	i = 0
	for num in odd_array:
		i += 1
		comp_array = odd_array[i:]
		for comp in comp_array:
			if gcd(num, 2 * comp) != 1:
				result += 1
	print(result)


from collections import defaultdict, Counter
from bisect import bisect, bisect_left
from math import sqrt, gcd, ceil, factorial
MOD = 10 ** 9 + 7
inf = float('inf')
ans_ = []

def nin():
	return int(input())

def ninf():
	return int(file.readline())

def st():
	return input().strip()

def stf():
	return file.readline().strip()

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

def readf():
	return list(map(int, file.readline().strip().split()))
ans_ = []

def solve():
	for _ in range(nin()):
		n = nin()
		arr = read()
		i = 0
		for j in range(n):
			if arr[j] % 2 == 0:
				(arr[i], arr[j]) = (arr[j], arr[i])
				i += 1
		c = 0
		for i in range(n):
			for j in range(i + 1, n):
				c += gcd(arr[i], 2 * arr[j]) > 1
		ans_.append(c)
solve()
for i in ans_:
	print(i)


import math
trails = int(input())
answer_list = []
for x in range(trails):
	n = int(input())
	numbers = input().split(' ')
	odds = []
	even = []
	ans = 0
	for t in numbers:
		use = int(t)
		if use % 2 == 1:
			odds.append(use)
		else:
			even.append(use)
	while even != []:
		d = even[0]
		ans = ans + len(even) + len(odds) - 1
		even.remove(d)
	while odds != []:
		d = odds[0]
		if d == 1:
			ans += 1
		for a in odds:
			gc = math.gcd(d, a)
			if gc > 1:
				ans += 1
		ans -= 1
		odds.remove(d)
	answer_list.append(ans)
for g in answer_list:
	print(g)


import math

def solve(n, arr):
	odd = []
	even = 0
	answer = 0
	for a in arr:
		if a % 2 == 0:
			even += 1
		else:
			odd.append(a)
	answer += even * n - even * (even + 1) // 2
	len_odd = len(odd)
	for i in range(len_odd):
		for j in range(i + 1, len_odd):
			answer += 1 if math.gcd(odd[i], odd[j]) > 1 else 0
	return answer

def main():
	n = int(input())
	arr = [int(a) for a in input().split()]
	print(solve(n, arr))
t = int(input())
while t > 0:
	main()
	t -= 1


from math import gcd

def main():
	for _ in range(int(input())):
		n = int(input())
		array = list(map(int, input().split()))
		odds = list()
		even = list()
		count = 0
		for x in array:
			if x & 1:
				odds.append(x)
			else:
				even.append(x)
		even += odds
		for i in range(n):
			for j in range(i + 1, n):
				if gcd(even[i], 2 * even[j]) > 1:
					count += 1
		print(count)
main()


from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = 0
	odds = []
	for x in a:
		if x % 2 == 0:
			k += 1
		else:
			odds.append(x)
	res = k * (k - 1) // 2 + k * len(odds)
	for i in range(len(odds) - 1):
		if odds[i] != 1:
			for j in range(i + 1, len(odds)):
				if gcd(odds[i], odds[j]) > 1:
					res += 1
	print(res)


import math
t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	even = []
	odd = []
	for item in a:
		if item % 2 == 0:
			even.append(item)
		else:
			odd.append(item)
	even.sort(reverse=True)
	odd.sort(reverse=True)
	even.extend(odd)
	good = 0
	for (i, ai) in enumerate(even[:-1]):
		result = [math.gcd(ai, 2 * aj) > 1 for aj in even[i + 1:]]
		good += sum(result)
	print(good)
	t -= 1


import math

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0

	def key_sort(num):
		return num % 2
	a.sort(key=key_sort)
	for i in range(n):
		for j in range(i + 1, n):
			if a[i] % 2 == 0 or math.gcd(a[i], a[j]) > 1:
				ans += 1
	print(ans)
T = int(input())
for _ in range(T):
	solve()


from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	ans = h = idx = 0
	b = sorted(a, key=lambda x: x % 2)
	for i in range(n):
		if b[i] % 2 == 0:
			ans += n - h - 1
			h += 1
			idx = i
	if h == 0:
		for i in range(len(b) - 1):
			for j in range(i + 1, len(b)):
				if gcd(b[i], b[j]) > 1:
					ans += 1
		print(ans)
	else:
		for i in range(idx + 1, len(b) - 1):
			for j in range(i + 1, len(b)):
				if gcd(b[i], b[j]) > 1:
					ans += 1
		print(ans)


import math
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	arr1 = []
	a = n - 1
	for i in range(n):
		if arr[i] % 2 == 0:
			ans += a
			a -= 1
		else:
			arr1.append(arr[i])
	for i in range(len(arr1)):
		for j in range(i + 1, len(arr1)):
			if math.gcd(arr1[i], arr1[j]) > 1:
				ans += 1
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	(e, o) = (0, 0)
	a = list(map(int, input().split()))
	b = []
	for i in range(n):
		t = a[i]
		if t % 2 == 0:
			e += 1
		elif t == 1:
			o += 1
		else:
			o += 1
			b += [t]
	f = 0
	k = len(b)
	for i in range(k):
		for j in range(i + 1, k):
			if math.gcd(b[i], b[j]) != 1:
				f += 1
	s = f + o * e + e * (e - 1) // 2
	print(s)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(o, e) = ([], [])
	cnt = 0
	for i in l:
		if i % 2 == 0:
			e.append(i)
		else:
			o.append(i)
	if len(o) == 0:
		print(len(e) * (len(e) - 1) // 2)
	else:
		for i in range(len(o)):
			for j in range(i + 1, len(o)):
				if math.gcd(o[i], o[j]) > 1:
					cnt = cnt + 1
		for i in range(n - 1, n - len(e) - 1, -1):
			cnt = cnt + i
		print(cnt)


import sys
from math import gcd, sqrt
sys.setrecursionlimit(10 ** 5)
inf = float('inf')
en = lambda x: list(enumerate(x))
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())

def solve():
	n = ii()
	arr = rr()
	brr = []
	for i in arr:
		if i % 2 == 0:
			brr += (i,)
	for i in arr:
		if i % 2:
			brr += (i,)
	c = 0
	for i in range(n):
		for j in range(i + 1, n):
			if i == j:
				continue
			if gcd(brr[i], 2 * brr[j]) > 1:
				c += 1
	print(c)
for _ in range(ii()):
	solve()


t = int(input())
import math

def answer(n, a):
	s = [[] for _ in range(16)]
	for i in range(n):
		ta = a[i]
		for j in range(1, 16):
			if ta % 2 ** j != 0:
				s[j - 1].append(ta)
				break
		if ta % 2 ** 15 == 0:
			s[15].append(ta)
	A = []
	for i in range(16):
		A.extend(s[15 - i])
	ans = 0
	for i in range(n - 1):
		ta = A[i]
		for j in range(i + 1, n):
			tb = 2 * A[j]
			if math.gcd(ta, tb) > 1:
				ans += 1
	print(ans)
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	answer(n, a)


from math import gcd
tests = int(input())
for _ in range(tests):
	input()
	primes = []
	test = list(map(int, input().split()))
	odd = [x for x in test if x & 1 == 1]
	even = sum([1 for x in test if x & 1 == 0])
	sol1 = sum([i for i in range(even)])
	sol2 = len(odd) * even
	sol3 = 0
	for e in range(len(odd)):
		for j in range(e + 1, len(odd)):
			if gcd(odd[e], odd[j]) > 1:
				sol3 += 1
	print(sol1 + sol2 + sol3)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	lst = input().split()
	lst = [int(i) for i in lst]
	cnt = 0
	gnp = n - 1
	gjl = []
	for i in lst:
		if i % 2 == 0:
			cnt += gnp
			gnp -= 1
		elif i > 1:
			gjl.append(i)
	for i in range(len(gjl)):
		for j in range(i + 1, len(gjl)):
			if math.gcd(gjl[i], gjl[j]) > 1:
				cnt += 1
	print(cnt)


from math import gcd
for _ in [0] * int(input()):
	n = int(input())
	t = 0
	(*a,) = map(int, input().split())
	b = [i for i in a if i % 2]
	k = len(b)
	for i in range(k - 1):
		for j in range(i + 1, k):
			t += gcd(b[i], b[j]) > 1
	print(n * (n - 1) // 2 - k * (k - 1) // 2 + t)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	l = []
	even = 0
	for i in a:
		if i % 2 == 0:
			even += 1
		elif i % 2 != 0 and i != 1:
			l.append(i)
	odd = n - even
	f = even / 2 * (2 * (n - 1) + (even - 1) * -1)
	a = 0
	if len(l) == 0:
		print(int(f))
	else:
		for i in range(len(l)):
			for j in range(i + 1, len(l)):
				if math.gcd(l[j], l[i]) > 1:
					a += 1
		print(a + int(f))


import math
import itertools

def main():
	import sys
	input = sys.stdin.readline
	inf = float('inf')
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		e = [a for a in l if a % 2 == 0]
		o = [a for a in l if a % 2 != 0]
		e.sort(reverse=True)
		o.sort(reverse=True)
		el = len(e)
		ol = len(o)
		s = el * n - el * (el + 1) // 2
		comb = itertools.combinations(o, 2)
		for i in list(comb):
			(x, y) = i
			if math.gcd(x, y) > 1:
				s += 1
		print(s)
main()


import math

def goodcount(numarr, n):
	ans = 0
	oddarr = []
	for i in numarr:
		if i % 2 != 0:
			oddarr.append(i)
	o = len(oddarr)
	e = n - o
	ans += int(n * (n - 1) / 2 - o * (o - 1) / 2)
	for j in range(o):
		for k in range(j + 1, o):
			if math.gcd(oddarr[j], oddarr[k]) > 1:
				ans += 1
	return ans
t = int(input())
for test in range(t):
	n = int(input())
	numarr = list(map(int, input().split()))
	print(goodcount(numarr, n))


import math
import itertools
t = int(input())

def test_case(num_list):
	pairs = 0
	even_list = []
	odd_list = []
	for i in range(n):
		if num_list[i] % 2 == 0:
			even_list.append(num_list[i])
		else:
			odd_list.append(num_list[i])
	final_list = even_list + odd_list
	for i in range(n):
		for j in range(i + 1, n):
			if math.gcd(final_list[i], 2 * final_list[j]) > 1:
				pairs += 1
	print(pairs)
for i in range(t):
	n = int(input())
	num_list = list(map(int, input().split()))
	test_case(num_list)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	c = []
	for i in range(n):
		if a[i] % 2 == 0:
			b.append(a[i])
		else:
			c.append(a[i])
	n1 = len(b)
	n2 = n - n1
	ans = n1 * n2 + n1 * (n1 - 1) // 2
	for i in range(n2 - 1):
		for j in range(i + 1, n2):
			if math.gcd(c[i], c[j]) > 1:
				ans += 1
	print(ans)


import math
count = int(input())
for _ in range(count):
	a = int(input())
	b = input().split()
	b = [int(i) for i in b]
	list_1 = [int(i) for i in b if i % 2 == 1]
	list_2 = [int(i) for i in b if i % 2 == 0]
	list_1.sort(reverse=True)
	list_2.sort(reverse=True)
	list_3 = list_2 + list_1
	constantine = 0
	while list_3:
		first = list_3.pop(0)
		for i in list_3:
			f = math.gcd(first, 2 * i)
			if f > 1:
				constantine += 1
	print(constantine)


import sys
import math
from collections import deque

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

def isprime(num):
	if num > 1:
		for i in range(2, int(num / 2) + 1):
			if num % i == 0:
				return False
		else:
			return True
	else:
		return False

def print_primes_till_n(n):
	(i, j, flag) = (0, 0, 0)
	a = []
	c = 0
	for i in range(1, n + 1, 1):
		if i == 1 or i == 0:
			continue
		flag = 1
		for j in range(2, i // 2 + 1, 1):
			if i % j == 0:
				flag = 0
				break
		if flag == 1:
			a.append(i)
			c += 1
	return (a, c)

def is_square(n):
	b = math.sqrt(n)
	if n == int(b * b):
		return True
	return False

def solution():
	for _ in range(int(input())):
		n = int(input())
		a = scan()
		a.sort()
		a.reverse()
		c = 0
		(c, b) = ([], [])
		for i in a:
			if i % 2 == 0:
				c.append(i)
			else:
				b.append(i)
		a = c + b
		(c, b) = (0, 0)
		for i in range(n):
			for j in range(i + 1, n):
				b = 2 * a[j]
				if math.gcd(a[i], b) > 1:
					c += 1
		print(c)
solution()


import math

def sol(A):
	even = []
	odd = []
	for a in A:
		if a % 2 == 0:
			even.append(a)
		else:
			odd.append(a)
	A = even + odd
	count = 0
	for i in range(len(A) - 1):
		for j in range(i + 1, len(A)):
			if math.gcd(A[i], 2 * A[j]) > 1:
				count += 1
	return count
x = int(input())
for _ in range(x):
	y = int(input())
	A = list(map(int, input().split()))
	print(sol(A))


from math import gcd
for _ in range(int(input())):
	a = int(input())
	o = []
	for x in input().split():
		if int(x) % 2 == 1:
			o.append(int(x))
	print((a - len(o)) * (a - len(o) - 1) // 2 + (a - len(o)) * len(o) + sum([1 if gcd(o[i], 2 * o[j]) > 1 else 0 for i in range(len(o)) for j in range(i + 1, len(o))]))


import math

def sol():
	n = int(input())
	a = [int(x) for x in input().split()]
	top = 0
	for i in range(n):
		if a[i] % 2 == 0:
			(a[top], a[i]) = (a[i], a[top])
			top += 1
	ans = 0
	for i in range(n):
		for j in range(i + 1, n):
			if math.gcd(a[i], 2 * a[j]) > 1:
				ans += 1
	print(ans)
for _ in range(int(input())):
	sol()


import sys
from math import gcd
for _ in range(int(input())):
	n = int(sys.stdin.readline())
	inp = list(map(int, sys.stdin.readline().split()))
	arr = []
	(even, ans) = (0, 0)
	for i in inp:
		if i % 2:
			arr.append(i)
		else:
			even += 1
	ans += even * (n - 1) - even * (even - 1) / 2
	for i in range(len(arr)):
		for j in range(i):
			if gcd(arr[i], arr[j]) > 1:
				ans += 1
	print(int(ans))


t = int(input())
import math
for i in range(t):
	n = int(input())
	arr = input().split(' ')
	(l_even, l_odd, good_i) = ([], [], 0)
	for j in range(n):
		if int(arr[j]) % 2 == 0:
			l_even.append(int(arr[j]))
		else:
			l_odd.append(int(arr[j]))
	for x in range(len(l_odd) - 1):
		for y in range(x + 1, len(l_odd)):
			if math.gcd(l_odd[x], l_odd[y]) > 1:
				good_i += 1
	print(len(l_odd) * len(l_even) + good_i + int(len(l_even) * (len(l_even) - 1) / 2))


from math import *
t = int(input())
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	odd = []
	tmp = 0
	for item in s:
		if item % 2 == 1:
			odd.append(item)
	for i in range(len(odd)):
		for j in range(i + 1, len(odd)):
			if gcd(odd[i], odd[j]) == 1:
				tmp += 1
	print(n * (n - 1) // 2 - tmp)


from math import gcd as g
t = int(input())
while t != 0:
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	(i, j) = (0, 0)
	while i < n:
		if a[i] % 2 == 0:
			(a[j], a[i]) = (a[i], a[j])
			j += 1
		i += 1
	for i in range(n - 1):
		for j in range(i + 1, n):
			if g(a[i], 2 * a[j]) > 1:
				ans += 1
	print(ans)
	t -= 1


from math import gcd
t = int(input())
for _ in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	even = [i for i in L if i % 2 == 0]
	odd = [i for i in L if i % 2 != 0]
	s = len(even) * (len(odd) + n - 1) // 2
	for i in range(len(odd)):
		for j in range(i + 1, len(odd)):
			if odd[i] != 1 and gcd(odd[i], odd[j]) > 1:
				s += 1
	print(s)


import sys
input = sys.stdin.readline
from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	c = []
	ans = 0
	for i in range(n):
		if a[i] % 2 == 0:
			b.append(a[i])
	for i in range(n):
		if a[i] % 2 == 1:
			c.append(a[i])
	for k in range(len(b)):
		ans += n - k - 1
	for i in range(len(c) - 1):
		for j in range(i + 1, len(c)):
			if gcd(c[i], 2 * c[j]) > 1:
				ans += 1
	print(ans)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	ans = 0
	arr = sorted(list((int(i) for i in input().split())), key=lambda x: x % 2)
	for i in range(n):
		for j in range(i + 1, n):
			if gcd(arr[i], 2 * arr[j]) > 1:
				ans += 1
	print(ans)


import math
t = int(input())
for k in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	c = 0
	all = []
	even = 0
	odd = []
	for i in range(n):
		if arr[i] % 2 == 0:
			all.append(arr[i])
			even = even + 1
		else:
			odd.append(arr[i])
	all = all + odd
	for i in range(even):
		if all[i] % 2 == 0:
			c = c + (n - i) - 1
	for i in range(len(odd)):
		for j in range(i + 1, len(odd)):
			if math.gcd(odd[i], 2 * odd[j]) > 1:
				c = c + 1
	print(c)


import math
for i in range(0, int(input())):
	n = int(input())
	l1 = [int(x) for x in input().split() if int(x) % 2 != 0]
	n1 = len(l1)
	ne = n - n1
	count = 0
	for j in range(0, n1):
		for x in range(j + 1, n1):
			if math.gcd(l1[j], 2 * l1[x]) > 1:
				count += 1
	print(int(count + ne / 2 * (2 * (n - 1) + (ne - 1) * -1)))


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	even = 0
	odd = []
	ans = 0
	for i in a:
		if i % 2 == 0:
			even = even + 1
		else:
			odd.append(i)
	ans = ans + even * (even - 1) // 2 + even * (n - even)
	for j in range(len(odd)):
		for k in range(j + 1, len(odd)):
			if math.gcd(odd[j], odd[k]) > 1:
				ans = ans + 1
	print(ans)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	odds = [x for x in a if x & 1 == 1]
	even_count = n - len(odds)
	count = n * even_count - even_count * (even_count + 1) // 2
	for i in range(len(odds)):
		for j in range(i + 1, len(odds)):
			if gcd(odds[i], odds[j]) != 1:
				count += 1
	print(count)


import math
num = int(input())
for _ in range(num):
	input()
	numb = [int(i) for i in input().split()]
	res = 0
	nums = []
	for num in numb:
		if num % 2 != 0:
			nums.append(num)
		else:
			nums.insert(0, num)
	for (i, a) in enumerate(nums):
		for b in nums[i + 1:]:
			if math.gcd(a, 2 * b) > 1:
				res = res + 1
	print(res)


import math
T = int(input())
for test in range(0, T):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = []
	num = 0
	for x in a:
		if x % 2 == 0:
			num += 1
		else:
			b.append(x)
	ans = 0
	for i in range(1, num + 1):
		ans += n - i
	xx = len(b)
	for i in range(0, xx):
		for j in range(i + 1, xx):
			if math.gcd(b[i], b[j]) > 1:
				ans += 1
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = []
	for ai in a:
		if ai % 2 == 1:
			b.append(ai)
	m = len(b)
	p = n - m
	ans = n * p - p * (p + 1) // 2
	for i in range(m):
		for j in range(i + 1, m):
			if math.gcd(b[i], b[j]) > 1:
				ans += 1
	print(ans)


import math
t = int(input())
for inh in range(0, t):
	(ev, od) = ([], [])
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(0, n):
		if a[i] % 2 == 0:
			ev.append(a[i])
		else:
			od.append(a[i])
	enlen = len(ev)
	odlen = len(od)
	ans = enlen * (enlen - 1) // 2
	ans += enlen * odlen
	for i in range(0, odlen - 1):
		k = od[i]
		if k != 1:
			for j in range(i + 1, odlen):
				g = math.gcd(k, od[j])
				if g > 1:
					ans += 1
	print(ans)


from math import gcd
ints = lambda : map(int, input().split())
li = lambda : list(map(int, input().split()))
for _ in range(int(input())):
	n = int(input())
	a = li()
	(even, l) = (0, 0)
	odd = []
	for i in a:
		if i % 2 == 0:
			even += 1
		else:
			odd.append(i)
			l += 1
	ans = even * (even - 1) // 2 + l * even
	if l == 0:
		print(ans)
		continue
	for i in range(l - 1):
		for j in range(i + 1, l):
			if gcd(odd[i], odd[j]) > 1:
				ans += 1
	print(ans)


n_infinity = float('inf')
mod = 1000000007
pi = 3.141592653589793
max_val = 10000002
import math

def main(n, arr):
	arr.sort(reverse=True)
	dp = []
	for i in arr:
		if i & 1 == 0:
			dp.append(i)
	for i in arr:
		if i & 1 == 1:
			dp.append(i)
	count = 0
	for i in range(n):
		for j in range(i + 1, n):
			x = math.gcd(dp[i], 2 * dp[j])
			if x > 1:
				count += 1
	return count
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(main(n, arr))


from collections import Counter as count
from bisect import bisect
import sys
from math import ceil, gcd
from itertools import groupby
input = lambda : sys.stdin.readline().rstrip('\r\n')
for i in range(int(input())):
	n = int(input())
	z = list(map(int, input().split()))
	(e, o) = ([], [])
	for i in z:
		if i % 2:
			o.append(i)
		else:
			e.append(i)
	z = e + o
	ans = 0
	for i in range(n):
		for j in range(i + 1, n):
			if gcd(z[i], z[j] * 2) > 1:
				ans += 1
	print(ans)


from math import gcd
for t in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())), key=lambda x: x % 2)
	ans = 0
	for i in range(n):
		for j in range(i + 1, n):
			ans += gcd(a[i], 2 * a[j]) != 1
	print(ans)


import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	e = 0
	a = []
	for i in range(n):
		if l[i] % 2 == 0:
			e = e + 1
		else:
			a.append(l[i])
	ans = e * n - e * (e + 1) // 2
	for i in range(len(a)):
		for j in range(i + 1, len(a)):
			if math.gcd(a[i], 2 * a[j]) > 1:
				ans = ans + 1
	print(ans)