An array of integers is called *good* if all its elements are perfect squares. 

You are given an array A of N integers. In one move, you can do the following:
Pick a subset of indices of the array, say \{i_{1}, i_{2}, \ldots, i_{k}\} where 1 ≤ i_{1} < i_{2} < \ldots < i_{k} ≤ N
Next, pick an integer X > 0
Finally, multiply the value at each chosen index by X, i.e, set A_{i_{j}} to A_{i_{j}} \cdot X for each 1 ≤ j ≤ k

Find the minimum number of moves required to make the array good.

Note: The value of X is fixed for a given move, but can vary between moves.

------ Input Format ------ 

- The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case contains two lines of input.
- The first line of each test case contains N, the size of the array.
- The second line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.

------ Output Format ------ 

For each testcase, output in a single line the minimum number of moves required to make the array good.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{4}$
$1 ≤ A_{i} ≤ 10^{8}$
- The sum of $N$ across all testcases won't exceed $10^{4}$.

------ subtasks ------ 

Subtask #1 (100 points): Original constraints

----- Sample Input 1 ------ 
5
3
15 2 4
4
15 14 4 9
3
10 3 6
2
4 9
2
2 8

----- Sample Output 1 ------ 
2
2
3
0
1

----- explanation 1 ------ 
Test case $1$: One possible sequence of moves is:
- Multiply the first element by $15$
- Multiply the second element by $2$

The array is now $[225, 4, 4] = [15^{2}, 2^{2}, 2^{2}]$, which is good.

Test case $3$: One possible sequence of moves is:
- Multiply the first and third elements by $8$
- Multiply the second and third elements by $3$
- Multiply the first element by $20$

The array is now $[1600, 9, 144] = [40^{2}, 3^{2}, 12^{2}]$, which is good.

Test case $4$: The array is already good, since $[4, 9] = [2^{2}, 3^{2}]$, so no moves need to be made.

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory

Mathematics


Solutions:
from collections import defaultdict
from math import sqrt

def prime_factors(n):
	p_fs = dict()
	if n % 2 == 0:
		p_fs[2] = 0
		while n % 2 == 0:
			p_fs[2] = 1 - p_fs[2]
			n //= 2
	for ii in range(3, int(sqrt(n)) + 1, 2):
		if n % ii == 0:
			p_fs[ii] = 0
			while n % ii == 0:
				n //= ii
				p_fs[ii] = 1 - p_fs[ii]
	if n != 1:
		p_fs[n] = 1
	return p_fs

def add(v1: list, v2: list):
	ans = list(set(v1).symmetric_difference(set(v2)))
	ans.sort()
	if ans:
		return (ans, ans[0])
	else:
		return (ans, -1)
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	primes = set()
	p_factors = defaultdict(list)
	n_rows = 0
	for i in range(N):
		pfs = prime_factors(A[i])
		for p in pfs:
			if pfs[p] & 1:
				p_factors[i].append(p)
				if p not in primes:
					primes.add(p)
		p_factors[i].sort()
		if p_factors[i]:
			n_rows += 1
	primes = sorted(list(primes))
	p_to_id = defaultdict(int)
	m = 0
	for p in primes:
		p_to_id[p] = m
		m += 1
	n_vs = 0
	w = defaultdict(list)
	for i in p_factors:
		if p_factors[i]:
			p = p_factors[i][0]
			k = p_to_id[p]
			v = [p_to_id[p] for p in p_factors[i]]
			v.sort()
			w[k].append(v)
	for i in range(m):
		if len(w[i]) > 1:
			f = w[i].pop()
			while w[i]:
				e = w[i].pop()
				(dif, ll) = add(f, e)
				if ll > i:
					w[ll].append(dif)
				elif ll == -1:
					n_rows -= 1
				else:
					raise RuntimeError('FUCK')
	print(n_rows)


import sys
from collections import defaultdict
from math import sqrt

def prime_factors(n):
	p_fs = dict()
	ct = 0
	if n % 2 == 0:
		p_fs[2] = 0
		while n % 2 == 0:
			p_fs[2] += 1
			n //= 2
		ct += 1
	for ii in range(3, int(sqrt(n)) + 1, 2):
		if n % ii == 0:
			p_fs[ii] = 0
			while n % ii == 0:
				n //= ii
				p_fs[ii] += 1
			ct += 1
	if n != 1:
		p_fs[n] = 1
		ct += 1
	return (p_fs, ct)

def add(v1: list, v2: list):
	indices = set(v1).union(set(v2))
	ans = []
	for idx in indices:
		if idx in v1 and idx not in v2 or (idx not in v1 and idx in v2):
			ans.append(idx)
	ans.sort()
	if ans:
		return (ans, ans[0])
	else:
		return (ans, -1)
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	primes = []
	p_factors = defaultdict(list)
	nrows = 0
	for i in range(N):
		(pfs, k) = prime_factors(A[i])
		for p in pfs:
			if pfs[p] & 1:
				p_factors[i].append(p)
				if p not in primes:
					primes.append(p)
		p_factors[i].sort()
		if p_factors[i]:
			nrows += 1
	primes.sort()
	p_to_id = defaultdict(int)
	id_to_p = defaultdict(int)
	m = 0
	for p in primes:
		p_to_id[p] = m
		id_to_p[m] = p
		m += 1
	n_vs = 0
	w = defaultdict(list)
	for i in p_factors:
		if p_factors[i]:
			p = p_factors[i][0]
			k = p_to_id[p]
			v = [p_to_id[p] for p in p_factors[i]]
			v.sort()
			w[k].append(v)
	for i in range(m):
		if len(w[i]) > 1:
			first = w[i].pop()
			while w[i]:
				e = w[i].pop()
				(e_, ll) = add(first, e)
				if ll > i:
					w[ll].append(e_)
				elif ll == -1:
					nrows -= 1
				else:
					print('FUCK', ll, first, e)
			w[i].append(first)
	print(nrows)