Let us call two integers $x$ and $y$ adjacent if $\frac{lcm(x, y)}{gcd(x, y)}$ is a perfect square. For example, $3$ and $12$ are adjacent, but $6$ and $9$ are not.

Here $gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$, and $lcm(x, y)$ denotes the least common multiple (LCM) of integers $x$ and $y$.

You are given an array $a$ of length $n$. Each second the following happens: each element $a_i$ of the array is replaced by the product of all elements of the array (including itself), that are adjacent to the current value.

Let $d_i$ be the number of adjacent elements to $a_i$ (including $a_i$ itself). The beauty of the array is defined as $\max_{1 \le i \le n} d_i$.

You are given $q$ queries: each query is described by an integer $w$, and you have to output the beauty of the array after $w$ seconds.


-----Input-----

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

The first line of each test case contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the length of the array.

The following line contains $n$ integers $a_1, \ldots, a_n$ ($1 \le a_i \le 10^6$) — array elements.

The next line contain a single integer $q$ ($1 \le q \le 3 \cdot 10^5$) — the number of queries.

The following $q$ lines contain a single integer $w$ each ($0 \le w \le 10^{18}$) — the queries themselves.

It is guaranteed that the sum of values $n$ over all test cases does not exceed $3 \cdot 10^5$, and the sum of values $q$ over all test cases does not exceed $3 \cdot 10^5$


-----Output-----

For each query output a single integer — the beauty of the array at the corresponding moment.


-----Examples-----

Input
2
4
6 8 4 2
1
0
6
12 3 20 5 80 1
1
1
Output
2
3


-----Note-----

In the first test case, the initial array contains elements $[6, 8, 4, 2]$. Element $a_4=2$ in this array is adjacent to $a_4=2$ (since $\frac{lcm(2, 2)}{gcd(2, 2)}=\frac{2}{2}=1=1^2$) and $a_2=8$ (since $\frac{lcm(8,2)}{gcd(8, 2)}=\frac{8}{2}=4=2^2$). Hence, $d_4=2$, and this is the maximal possible value $d_i$ in this array.

In the second test case, the initial array contains elements $[12, 3, 20, 5, 80, 1]$. The elements adjacent to $12$ are $\{12, 3\}$, the elements adjacent to $3$ are $\{12, 3\}$, the elements adjacent to $20$ are $\{20, 5, 80\}$, the elements adjacent to $5$ are $\{20, 5, 80\}$, the elements adjacent to $80$ are $\{20, 5, 80\}$, the elements adjacent to $1$ are $\{1\}$. After one second, the array is transformed into $[36, 36, 8000, 8000, 8000, 1]$.

Difficulty: HARD
Tags: Bit manipulation

Graph algorithms

String algorithms

Number theory

Mathematics
Skill types: Bit manipulation

Starter code:

Solutions:
import collections
import sys

def generate_primes(max_number):
	is_prime = [True] * (max_number + 1)
	is_prime[1] = False
	primes = []
	i = 2
	while i * i <= max_number:
		if is_prime[i]:
			primes.append(i)
			j = i * i
			while j <= max_number:
				is_prime[j] = False
				j += i
		i += 1
	return (primes, is_prime)

def get_bucket(n, primes, is_prime):
	bucket = 1
	for prime in primes:
		if n == 1:
			return bucket
		if is_prime[n]:
			bucket *= n
			break
		count = 0
		while n % prime == 0:
			n //= prime
			count += 1
		if count % 2 == 1:
			bucket *= prime
	return bucket
(primes, is_prime) = generate_primes(1000000)
for _ in range(int(input())):
	n = int(sys.stdin.readline())
	xs = map(int, sys.stdin.readline().split(' '))
	count_by_bucket1 = collections.defaultdict(int)
	for x in xs:
		bucket = get_bucket(x, primes, is_prime)
		count_by_bucket1[bucket] += 1
	max_bucket_size1 = max(count_by_bucket1.values())
	count_by_bucket2 = collections.defaultdict(int)
	for (bucket, count) in count_by_bucket1.items():
		if count % 2 == 0:
			new_bucket = 1
		else:
			new_bucket = bucket
		count_by_bucket2[new_bucket] += count
	max_bucket_size2 = max(count_by_bucket2.values())
	num_queries = int(sys.stdin.readline())
	for _ in range(num_queries):
		w = int(sys.stdin.readline())
		if w == 0:
			sys.stdout.write(f'{max_bucket_size1}\n')
		else:
			sys.stdout.write(f'{max_bucket_size2}\n')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
from bisect import bisect_left as bsl

def main():
	primes = [2]
	for s in range(3, int(math.sqrt(10 ** 6)) + 2, 2):
		ind = min(bsl(primes, int(math.sqrt(s)) + 1), len(primes) - 1)
		broke = False
		for i in range(ind + 1):
			if s % primes[i] == 0:
				broke = True
				break
		if broke == False:
			primes.append(s)
	for j in range(int(input())):
		n = int(input())
		vals = list(map(int, input().split()))
		sq = []
		nsq = []
		for s in range(n):
			if int(math.sqrt(vals[s])) ** 2 == vals[s]:
				sq.append(vals[s])
			else:
				nsq.append(vals[s])
		dict1 = {}
		sec0 = len(sq)
		sec1 = len(sq)
		for i in nsq:
			temp = i
			ind = min(bsl(primes, math.ceil(math.sqrt(i)) + 1), len(primes) - 1)
			tt = []
			for s in range(ind + 1):
				if temp % primes[s] == 0:
					count = 0
					while temp % primes[s] == 0:
						temp //= primes[s]
						count += 1
					if count % 2 == 1:
						tt.append(primes[s])
			if temp != 1:
				tt.append(temp)
			tt = tuple(tt)
			if not tt in dict1:
				dict1[tt] = 1
			else:
				dict1[tt] += 1
			sec0 = max(dict1[tt], sec0)
		for i in dict1.values():
			if i % 2 == 0:
				sec1 += i
		if len(dict1) > 0:
			sec1 = max(sec1, max(dict1.values()))
		q = int(input())
		for s in range(q):
			w = int(input())
			if w == 0:
				print(sec0)
			else:
				print(sec1)
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):

	def __init__(self, file):
		self.newlines = 0
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

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

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

def N():
	return int(input())

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

def print_list(l):
	print(' '.join(map(str, l)))
from functools import lru_cache
from collections import Counter
M = 10 ** 6 + 1

def getPrimes(n):
	if n < 3:
		return []
	output = [1] * n
	(output[0], output[1]) = (0, 0)
	for i in range(2, int(n ** 0.5) + 1):
		if output[i]:
			output[i * i:n:i] = [0] * ((n - 1 - i * i) // i + 1)
	return [i for i in range(n) if output[i] == 1]
primes = getPrimes(1000)
primes = [v ** 2 for v in primes]

@lru_cache(1000000)
def get(v):
	for p in primes:
		if p > v:
			break
		while v % p == 0:
			v //= p
	return v
for _ in range(N()):
	n = N()
	a = RLL()
	k = Counter()
	for v in a:
		k[get(v)] += 1
	(d1, d2) = (k[1], k[1])
	del k[1]
	for count in k.values():
		if count & 1 == 0:
			d1 += count
		if count > d2:
			d2 = count
	d1 = max(d1, d2)
	for _ in range(N()):
		if N() == 0:
			print(d2)
		else:
			print(d1)


import sys, os, io
input = sys.stdin.readline

def sieve(n):
	is_prime = [True for _ in range(n + 1)]
	is_prime[1] = False
	for i in range(2, n + 1):
		if is_prime[i]:
			j = 2 * i
			while j <= n:
				is_prime[j] = False
				j += i
	table = [i * i for i in range(1, n + 1) if is_prime[i]]
	return table
from collections import Counter
primes = sieve(1001)
T = int(input())
ans = []
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	for i in range(N):
		for p in primes:
			if p > A[i]:
				break
			while A[i] % p == 0:
				A[i] //= p
	cnts = Counter(A)
	zero = max(cnts.values())
	one = 0
	for (k, v) in cnts.items():
		if k == 1 or v % 2 == 0:
			one += v
	one = max(zero, one)
	Q = int(input())
	for i in range(Q):
		w = int(input())
		if w == 0:
			ans.append(zero)
		else:
			ans.append(one)
print(*ans, sep='\n')


import sys
from os import environ
from collections import defaultdict
if environ['USERNAME'] == 'kissz':
	inp = open('in0.txt', 'r').readline

	def debug(*args):
		print(*args, file=sys.stderr)
else:
	inp = sys.stdin.readline

	def debug(*args):
		pass
lookup = [i for i in range(1000001)]
for i in range(2, 1001):
	i2 = i ** 2
	for j in range(i2, 1000001, i2):
		lookup[j] = j // i2
for _ in range(int(inp())):
	inp()
	X = [*map(int, inp().split())]
	q = int(inp())
	classes = defaultdict(int)
	for x in X:
		classes[lookup[x]] += 1
	beauty = max(classes.values())
	ans = [beauty, max(beauty, classes[1] + sum((cnt for (cl, cnt) in classes.items() if not cnt % 2 and cl > 1)))]
	for _ in range(q):
		w = int(inp())
		print(ans[w > 0])

def create_test():
	from random import randint
	with open('in0.txt', 'w') as f:
		print(1, file=f)
		print(300000, file=f)
		print(*[randint(1, 1000000) for _ in range(300000)], file=f)
		print(300000, file=f)
		for _ in range(300000):
			print(randint(0, 1), file=f)


from collections import Counter
from sys import stdin

def calc_rep(n):
	rep = [1] * (n + 1)
	s = 1
	while s * s <= n:
		f = 1
		while s * s * f <= n:
			rep[s * s * f] = f
			f += 1
		s += 1
	return rep
rep = calc_rep(10 ** 6)
tc = int(stdin.readline())
for _ in range(tc):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	c = Counter((rep[x] for x in a))
	d = Counter()
	for (k, v) in c.items():
		if v % 2 == 1:
			d[k] += v
		else:
			d[1] += v
	res = [c.most_common(1)[0][1], d.most_common(1)[0][1]]
	q = int(stdin.readline())
	r = []
	for _ in range(q):
		w = stdin.readline()
		r.append(res[0] if w.strip() == '0' else res[1])
	print('\n'.join(map(str, r)))


from sys import stdin
T = int(stdin.readline())
dct = {i: i for i in range(1000001)}
for i in range(2, 1001):
	for j in range(1, 10 ** 6 // i ** 2 + 1):
		dct[i ** 2 * j] = j
for _ in range(T):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	q = int(stdin.readline())
	seen = {}
	for i in range(n):
		num = dct[arr[i]]
		if num not in seen:
			seen[num] = 1
		else:
			seen[num] += 1
	max1 = 1
	max2 = 0
	for val in seen.values():
		max1 = max(max1, val)
		if val % 2 == 0:
			max2 += val
	if 1 in seen:
		if seen[1] % 2 == 0:
			pass
		else:
			max2 += seen[1]
	for k in range(q):
		if int(stdin.readline()) >= 1:
			print(max(max1, max2))
		else:
			print(max1)


import os
import sys
from io import BytesIO, IOBase
from collections import Counter

def seieve_prime_factorisation(n):
	(p, i) = ([1] * (n + 1), 2)
	while i * i <= n:
		if p[i] == 1:
			for j in range(i * i, n + 1, i):
				p[j] = i
		i += 1
	return p

def prime_factorisation_by_seive(p, x):
	c = Counter()
	while p[x] != 1:
		c[p[x]] += 1
		x = x // p[x]
	c[x] += 1
	return c

def main():
	p = seieve_prime_factorisation(10 ** 6)
	for _ in range(int(input())):
		input()
		a = list(map(int, input().split()))
		b = Counter()
		for i in a:
			z = prime_factorisation_by_seive(p, i)
			y = 1
			for j in z:
				if z[j] & 1:
					y *= j
			b[y] += 1
		ma = b[max(b, key=b.get)]
		maa = 0
		for i in b:
			if i == 1 or not b[i] & 1:
				maa += b[i]
		maa = max(ma, maa)
		for i in range(int(input())):
			if not int(input()):
				print(ma)
			else:
				print(maa)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import defaultdict as dd
import sys
input = sys.stdin.buffer.readline

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))
MAXPRIME = 10 ** 6
isPrime = [0 for _ in range(MAXPRIME + 1)]
isPrime[0] = -1
isPrime[1] = -1
for i in range(2, MAXPRIME // 2 + 1):
	if isPrime[i] == 0:
		for multiple in range(i * i, MAXPRIME + 1, i):
			if isPrime[multiple] == 0:
				isPrime[multiple] = i

def getPrimeFactorRepresentation(x):
	primeFactorCnts = dd(lambda : 0)
	while True:
		p = isPrime[x]
		if p == 0:
			primeFactorCnts[x] += 1
			break
		if p == -1:
			break
		primeFactorCnts[p] += 1
		x //= p
	res = 1
	for (k, v) in primeFactorCnts.items():
		if v % 2 == 1:
			res *= k
	return res
allAns = []
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	cntsZeroSeconds = dd(lambda : 0)
	for x in a:
		p = getPrimeFactorRepresentation(x)
		cntsZeroSeconds[p] += 1
	cntsOneSecondAndBeyond = dd(lambda : 0)
	for (value, cnt) in cntsZeroSeconds.items():
		if value == 1:
			cntsOneSecondAndBeyond[1] += cnt
		elif cnt % 2 == 0:
			cntsOneSecondAndBeyond[1] += cnt
		else:
			cntsOneSecondAndBeyond[value] += cnt
	zeroSecAns = max(cntsZeroSeconds.values())
	oneSecAndBeyondAns = max(cntsOneSecondAndBeyond.values())
	q = int(input())
	for __ in range(q):
		w = int(input())
		if w == 0:
			allAns.append(zeroSecAns)
		else:
			allAns.append(oneSecAndBeyondAns)
multiLineArrayPrint(allAns)


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
primes = []
for i in range(2, 1001):
	flag = 0
	for j in range(2, i):
		if i % j == 0:
			flag = 1
			break
	if flag == 0:
		primes.append(i)
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	dic = {}
	for i in a:
		curr = 1
		for p in primes:
			if i == 1:
				break
			count = 0
			while i % p == 0:
				i //= p
				count += 1
			if count % 2 == 1:
				curr *= p
		curr *= i
		if curr in dic:
			dic[curr] += 1
		else:
			dic[curr] = 1
	ans1 = 0
	ans2 = 0
	for s in dic:
		ans1 = max(ans1, dic[s])
	if 1 in dic:
		ans2 += dic[1]
	for s in dic:
		if s == 1:
			continue
		if dic[s] % 2 == 0:
			ans2 += dic[s]
	if ans2 == 0:
		ans2 = 1
	q = int(input())
	for i in range(q):
		w = int(input())
		if w == 0:
			print(ans1)
		else:
			print(max(ans1, ans2))


import sys
input = sys.stdin.readline
from collections import Counter
Primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
t = int(input())
for tests in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	B = []
	for a in A:
		for p in Primes:
			while a % p ** 2 == 0:
				a //= p ** 2
		B.append(a)
	C = Counter(B)
	MAX = 0
	EVEN = 0
	for c in C:
		MAX = max(MAX, C[c])
		if C[c] % 2 == 0 or c == 1:
			EVEN += C[c]
	q = int(input())
	for queries in range(q):
		w = int(input())
		if w == 0:
			print(MAX)
		else:
			print(max(MAX, EVEN))


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
start_time = time.time()

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def isInt(s):
	return '0' <= s[0] <= '9'
MOD = 10 ** 9 + 7
squares = []
for i in range(1, 1001):
	squares.append(i * i)
adj_class = [0] * (10 ** 6 + 1)
curr = 0
for i in range(1, 10 ** 6 + 1):
	if not adj_class[i]:
		curr += 1
		for sq in squares:
			if sq * i > 10 ** 6:
				break
			adj_class[sq * i] = curr

def solve():
	N = getInt()
	A = getInts()
	max_val = 0
	counts = dd(int)
	for a in A:
		counts[adj_class[a]] += 1
	max_odds = 0
	total_evens = 0
	max_val = 0
	for (key, x) in counts.items():
		if x % 2 == 1 and key > 1:
			max_odds = max(max_odds, x)
		else:
			total_evens += x
		max_val = max(max_val, x)
	q = getInt()
	for _ in range(q):
		x = getInt()
		if x >= 1:
			print(max(total_evens, max_odds))
		else:
			print(max_val)
	return
for _ in range(getInt()):
	solve()


import sys
input = sys.stdin.readline
for f in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	v = {}
	for x in a:
		f = []
		i = 3
		c = 0
		while x % 2 == 0:
			x //= 2
			c += 1
		if c % 2 == 1:
			f.append(2)
		while i * i <= x:
			if x % i == 0:
				c = 0
				while x % i == 0:
					c += 1
					x //= i
				if c % 2 == 1:
					f.append(i)
			i += 2
		if x > 1:
			f.append(x)
		f = tuple(f)
		if f in v:
			v[f] += 1
		else:
			v[f] = 1
	v0 = 1
	vx = 0
	for x in v:
		if x == tuple([]) or v[x] > 1:
			v0 = max(v0, v[x])
			if v[x] % 2 == 0 or x == tuple([]):
				vx += v[x]
	vx = max(vx, v0)
	for i in range(q):
		w = int(input())
		if w == 0:
			print(v0)
		else:
			print(vx)


from sys import stdin
dct = {i: i for i in range(1000001)}
for i in range(2, 1001):
	for j in range(1, 10 ** 6 // i ** 2 + 1):
		dct[i ** 2 * j] = j
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	elements = map(int, stdin.readline().split())
	q = int(stdin.readline())
	dct2 = {}
	for i in elements:
		if dct[i] not in dct2:
			dct2[dct[i]] = 1
		else:
			dct2[dct[i]] += 1
	chan = 0
	maxx = 0
	for (so, gia) in dct2.items():
		if so == 1:
			maxx = max(gia, maxx)
			chan += gia
		else:
			maxx = max(gia, maxx)
			if gia % 2 == 0:
				chan += gia
	maxx2 = max(chan, maxx)
	for times in range(q):
		quer = stdin.readline()
		if quer == '0\n':
			print(maxx)
		else:
			print(maxx2)


import sys
input = lambda : sys.stdin.readline().rstrip()

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 7, 61] if n < 1 << 32 else [2, 3, 5, 7, 11, 13, 17] if n < 1 << 48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += i % 2 + (3 if i % 3 == 1 else 1)
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(N):
	pf = primeFactor(N)
	ret = [1]
	for p in pf:
		ret_prev = ret
		ret = []
		for i in range(pf[p] + 1):
			for r in ret_prev:
				ret.append(r * p ** i)
	return sorted(ret)

def squareFree(n):
	pf = primeFactor(n)
	s = 1
	for p in pf:
		s *= p ** (pf[p] % 2)
	return s
T = int(input())
for _ in range(T):
	N = int(input())
	A = [squareFree(int(a)) for a in input().split()]
	D = {}
	for a in A:
		if a not in D:
			D[a] = 1
		else:
			D[a] += 1
	D2 = {}
	for d in D.keys():
		v = d if D[d] % 2 else 1
		if v not in D2:
			D2[v] = D[d]
		else:
			D2[v] += D[d]
	X = [max(D.values()), max(D2.values())]
	Q = int(input())
	for _ in range(Q):
		q = int(input())
		print(X[min(q, 1)])


import sys
import collections
import math
input = sys.stdin.readline
mnum = 10 ** 6 + 1000
mnumsqr = math.ceil(math.sqrt(mnum)) + 10
mCanDivSqrt = [-1] * (mnum + 10)
for i in range(2, mnumsqr):
	if i ** 2 < mnum + 1:
		cur = i ** 2
		x = cur
		while x <= mnum:
			mCanDivSqrt[x] = i ** 2
			x += cur

def do():
	n = int(input())
	dat = list(map(int, input().split()))
	numbTable = collections.defaultdict(int)
	for x in dat:
		while True:
			if mCanDivSqrt[x] != -1:
				x //= mCanDivSqrt[x]
			else:
				break
		numbTable[x] += 1
	nextBnum1 = numbTable[1]
	res0 = max(nextBnum1, 1)
	for k in numbTable.keys():
		if k == 1:
			continue
		res0 = max(res0, numbTable[k])
		if numbTable[k] % 2 == 0:
			nextBnum1 += numbTable[k]
	nextBnum1 = max(nextBnum1, res0)
	q = int(input())
	for _ in range(q):
		qnum = int(input())
		if qnum == 0:
			print(res0)
		else:
			print(nextBnum1)
q = int(input())
for _ in range(q):
	do()


import sys, io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
MAX = 10 ** 6 + 5
find = list(range(MAX))
for i in range(1, 1001):
	for j in range(0, MAX, i * i):
		find[j] = j // i // i
t = int(input())
out = []
for _ in range(t):
	n = int(input())
	counts = dict()
	best = 0
	for v in map(int, input().split()):
		u = find[v]
		if u not in counts:
			counts[u] = 0
		counts[u] += 1
		best = max(best, counts[u])
	tol = 0
	for u in counts:
		if u == 1 or counts[u] % 2 == 0:
			tol += counts[u]
	q = int(input())
	for _ in range(q):
		v = int(input())
		if v == 0:
			out.append(best)
		else:
			out.append(max(best, tol))
print('\n'.join(map(str, out)))


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

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

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

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

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	ans = {}
	for p in range(n + 1):
		if prime[p]:
			ans[p] = 1
	return ans

def sieve():
	MAXN = 10 ** 6 + 1
	spf = [0 for i in range(MAXN)]
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
	return spf

def main(spf):
	try:
		n = I()
		l = list(In())
		d = {}
		used = {}
		for x in l:
			if used.get(x, -1) != -1:
				temp = used[x]
			else:
				z = {}
				X = x
				while x != 1:
					pa = spf[x]
					if z.get(pa, -1) != -1:
						z[pa] += 1
						z[pa] %= 2
					else:
						z[pa] = 1
					x = x // spf[x]
				temp = 1
				for y in z:
					temp *= y ** z[y]
				used[X] = temp
			if d.get(temp, -1) != -1:
				d[temp] += 1
			else:
				d[temp] = 1
		(a, b) = (0, 0)
		for x in d:
			if x == 1 or d[x] % 2 == 0:
				b += d[x]
			a = max(a, d[x])
		for q in range(I()):
			Q = I()
			if Q == 0:
				print(a)
			else:
				print(max(a, b))
	except:
		pass
M = 998244353
P = 1000000007
spf = sieve()
for _ in range(I()):
	main(spf)


from sys import stdin
input = stdin.readline

def calculate():
	a = [i for i in range(10 ** 6 + 1)]
	for square_root in range(1000, 1, -1):
		square = square_root ** 2
		x = square
		while x <= 10 ** 6:
			if a[x] % square == 0:
				a[x] //= square
			x += square
	return a

def main(input):
	precalculated = calculate()
	t = int(input())
	for _ in range(t):
		n = int(input())
		d = {}
		for ai in map(int, input().split()):
			sai = precalculated[ai]
			d[sai] = d.get(sai, 0) + 1
		c_1 = d.get(1, 0)
		c_even = 0
		mx = 0
		for (k, c) in d.items():
			if c % 2 == 0 and k != 1:
				c_even += c
			if c > mx:
				mx = c
		w0 = mx
		w1 = max(mx, c_1 + c_even)
		q = int(input())
		for _ in range(q):
			w = int(input())
			print(w0 if w == 0 else w1)
main(input)


import sys
input = sys.stdin.readline

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		dic = {r: [] for r in self.roots()}
		for i in range(self.n):
			dic[self.find(i)].append(i)
		return dic

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))
from collections import defaultdict
div_s = [4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, 2809, 3481, 3721, 4489, 5041, 5329, 6241, 6889, 7921, 9409, 10201, 10609, 11449, 11881, 12769, 16129, 17161, 18769, 19321, 22201, 22801, 24649, 26569, 27889, 29929, 32041, 32761, 36481, 37249, 38809, 39601, 44521, 49729, 51529, 52441, 54289, 57121, 58081, 63001, 66049, 69169, 72361, 73441, 76729, 78961, 80089, 85849, 94249, 96721, 97969, 100489, 109561, 113569, 120409, 121801, 124609, 128881, 134689, 139129, 143641, 146689, 151321, 157609, 160801, 167281, 175561, 177241, 185761, 187489, 192721, 196249, 201601, 208849, 212521, 214369, 218089, 229441, 237169, 241081, 249001, 253009, 259081, 271441, 273529, 292681, 299209, 310249, 316969, 323761, 326041, 332929, 344569, 351649, 358801, 361201, 368449, 375769, 380689, 383161, 398161, 410881, 413449, 418609, 426409, 434281, 436921, 452929, 458329, 466489, 477481, 491401, 502681, 516961, 528529, 537289, 546121, 552049, 564001, 573049, 579121, 591361, 597529, 619369, 635209, 654481, 657721, 674041, 677329, 683929, 687241, 703921, 727609, 734449, 737881, 744769, 769129, 776161, 779689, 786769, 822649, 829921, 844561, 863041, 877969, 885481, 896809, 908209, 935089, 942841, 954529, 966289, 982081, 994009]

def main():
	n = int(input())
	alst = list(map(int, input().split()))
	dd = defaultdict(int)
	UF = UnionFind(n)
	one = 0
	for (i, a) in enumerate(alst, 1):
		for d in div_s:
			while a % d == 0:
				a //= d
		if dd[a] == 0:
			dd[a] = i
		else:
			UF.union(i - 1, dd[a] - 1)
		if a == 1:
			one += 1
	ans1 = 0
	ans2 = 0
	for r in UF.roots():
		s = UF.size(r)
		ans1 = max(ans1, s)
		if s % 2 == 0:
			ans2 += s
	if one % 2 == 1:
		ans2 += one
	ans2 = max(ans1, ans2)
	for _ in range(int(input())):
		w = int(input())
		if w == 0:
			print(ans1)
		else:
			print(ans2)
for _ in range(int(input())):
	main()