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

int [] prepare (int limit)
{
	auto res = limit.iota.array;
	for (int d = 2; d * d < limit; d++)
	{
		if (res[d] == d)
		{
			for (int e = d * d; e < limit; e += d)
			{
				if (res[e] == e)
				{
					res[e] = d;
				}
			}
		}
	}
	return res;
}

int [] roots (int limit)
{
	auto p = prepare (limit);
	auto res = new int [limit];
	foreach (d; 0..limit)
	{
		int cur = d;
		res[d] = 1;
		while (cur > 1)
		{
			bool parity = 0;
			int x = p[cur];
			while (cur % x == 0)
			{
				cur /= x;
				parity ^= 1;
			}
			if (parity)
			{
				res[d] *= x;
			}
		}
	}
	return res;
}

immutable int limit = 10 ^^ 6 + 5;

void main ()
{
	auto r = roots (limit);

	auto tests = readln.strip.to !(int);
	foreach (test; 0..tests)
	{
		auto n = readln.strip.to !(int);
		auto a = readln.splitter.map !(to !(int)).array;

		int [int] nums;
		foreach (ref c; a)
		{
			nums[r[c]] += 1;
		}

		auto answer = [0, 0, 0];
		foreach (step; 0..3)
		{
			debug {writeln (nums);}
			int [int] next;
			foreach (k, v; nums)
			{
				answer[step] = max (answer[step], v);
				int p = (v & 1) ? k : 1;
				next[p] += v;
			}
			nums = next;
		}

		auto q = readln.strip.to !(int);
		foreach (s; 0..q)
		{
			auto z = readln.strip.to !(long);
			writeln (answer[min (z, $ - 1).to !(int)]);
		}
	}
}
