import std.algorithm;
import std.conv;
import std.numeric;
import std.range;
import std.stdio;
import std.string;

void main ()
{
	auto tests = readln.strip.to !(int);
	foreach (test; 0..tests)
	{
		auto n = readln.strip.to !(int);
		auto a = readln.splitter.map !(to !(int)).array;
		auto lo = a.filter !(x => (x & 1) == 0).array;
		auto hi = a.filter !(x => (x & 1) == 1).array;
		auto b = lo ~ hi;
		int res = 0;
		foreach (i; 0..n)
		{
			foreach (j; i + 1..n)
			{
				if (gcd (b[i], b[j] * 2) > 1)
				{
					res += 1;
				}
			}
		}
		writeln (res);
	}
}
