Given a sequence of $n$ numbers, $D=(d_1,d_2,\ldots,d_n)$, what's the maximum size of a subsequence of $\mbox{D}$ in which every pair is a nice pair?

The pair $(a,b)$ is a nice pair iff at least one of the following condition holds.  

The parity of the number of distinct prime divisors of $\boldsymbol{a}$ is equal to that of $\boldsymbol{b}$. For example, $\mbox{18}$ has two distinct prime divisors: $2$ and $3$.  
The parity of the sum of all positive divisors of $\boldsymbol{a}$ is equal to that of $\boldsymbol{b}$.

Input Format

The first line contains a single integer $n$. The second line contains $n$ space-separated integers $d_1,d_2,\ldots,d_n$. 

Constraints

$1\leq n\leq200$
$1\leq d_i\leq10^{15}$  

Output Format

Print the maximum size of any subsequence of $\mbox{D}$ in which every pair is a nice pair.

Sample Input 0
4
2 3 6 8

Sample Output 0
3

Explanation 0

  d
  Prime divisors (count)
  Divisors (sum)

  2
  2 (1)
  1, 2 (3)

  3
  3 (1)
  1, 3 (4)

  6
  2, 3 (2)
  1, 2, 3, 6 (12)

  8
  2 (1)
  1, 2, 4, 8 (15)

You can verify that the pairs $(d_1,d_2),(d_1,d_4),(d_2,d_3),(d_2,d_4)$ are nice, while $(d_1,d_3)$ and $(d_3,d_4)$ are not.  

The largest subsequence of $\mbox{D}$ in which all pairs are nice pairs is $(2,3,8)$ and its size is $3$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Number theory


Solutions:
import random
import math

def isPrime(n, k):
	nn = n - 1
	s = 1
	while nn % 2 ** s == 0:
		s += 1
	s -= 1
	d = int(nn // 2 ** s)
	for i in range(k):
		a = random.randint(2, n - 1)
		x = pow(a, d, n)
		if x == 1 or x == n - 1:
			continue
		flag = True
		for r in range(1, s):
			x = pow(x, 2, n)
			if x == 1:
				return False
			if x == n - 1:
				flag = False
				break
		if not flag:
			continue
		return False
	return True
n = int(input())
tab11 = 0
tab10 = 0
tab01 = 0
tab00 = 0
D = input().split()
n = len(D)
for i in range(n):
	tmp = int(D[i])
	somme = 1
	count = 0
	if not tmp & 1:
		count = 1
		tmp = tmp >> 1
		while not tmp & 1:
			tmp = tmp >> 1
	j = 3
	if tmp % j == 0:
		nbenter = 1
		count = count + 1
		tmp = tmp / j
		while tmp % j == 0:
			nbenter += 1
			tmp = tmp / j
		if nbenter & 1:
			somme = 0
	j = 5
	if tmp % j == 0:
		nbenter = 1
		count = count + 1
		tmp = tmp / j
		while tmp % j == 0:
			nbenter += 1
			tmp = tmp / j
		if nbenter & 1:
			somme = 0
	exit100k = 0
	j = 5
	while j * j <= tmp:
		j += 2
		if j * j * j > tmp:
			exit100k = 1
			break
		if tmp % j == 0:
			nbenter = 1
			count = count + 1
			tmp = tmp / j
			while tmp % j == 0:
				nbenter += 1
				tmp = tmp / j
			if nbenter & 1:
				somme = 0
	if exit100k & 1:
		exit100k = math.floor(math.sqrt(tmp))
		if exit100k * exit100k == tmp:
			count += 1
		else:
			somme = 0
			if isPrime(int(tmp), 50):
				count += 1
	elif tmp > 1:
		somme = 0
		count += 1
	if count & 1:
		if somme & 1:
			tab11 += 1
		else:
			tab10 += 1
	elif somme & 1:
		tab01 += 1
	else:
		tab00 += 1
maxi = max(tab11 + tab10, tab11 + tab01, tab00 + tab10, tab00 + tab01)
print(maxi)


import sys
from time import time

def prime_gen(n):
	sieve = [1] * n
	for p in range(2, n):
		if sieve[p]:
			yield p
			for i in range(p + p, n, p):
				sieve[i] = 0

def pf_gen(n, pp):
	for p in pp:
		if p > n:
			break
		cnt = 0
		while n % p == 0:
			cnt += 1
			n //= p
		if cnt:
			yield (p, cnt)
	if n > 1:
		r = int(pow(n, 0.5))
		if r * r == n:
			yield (r, 2)
		else:
			yield (n, 1)

def get_sigmas(n, pp):
	(s0, s1) = (0, 1)
	for (p, c) in pf_gen(n, pp):
		s0 += 1
		s1 *= (pow(p, c + 1) - 1) // (p - 1)
	return (s0, s1)

def solve(aa):
	mx = max(aa)
	n = int(pow(mx, 1 / 3))
	tm = time()
	pp = list(prime_gen(n + 2500000))
	print('\tprimes generated: n=%d total=%d time elapsed=%s' % (n, len(pp), time() - tm), file=sys.stderr)
	cache = [0] * 4
	for a in aa:
		(s0, s1) = get_sigmas(a, pp)
		(p0, p1) = (s0 % 2, s1 % 2)
		cache[p0 + 2 * p1] += 1
	return max((cache[0] + cache[1], cache[0] + cache[2], cache[1] + cache[3], cache[2] + cache[3]))

def test(fr, to):
	aa = list(range(fr, to))
	return solve(aa)
tm = time()
_ = int(input())
aa = list(map(int, input().split()))
print(solve(aa))
print('time elapsed: %s' % (time() - tm,), file=sys.stderr)


N = 10 ** 6
T = [1] * N
(T[0], T[1]) = (0, 0)
for i in range(4, N, 2):
	T[i] = 0
q = 3
while q <= int(N ** 0.5):
	if T[q]:
		for i in range(q * q, N, 2 * q):
			T[i] = 0
	q += 2
pl = [i for i in range(N) if T[i]]

def nbdivsumdiv(n):
	i = 0
	nb = 0
	sumdiv = 1
	while pl[i] <= int(n ** (1 / 3)) + 10 and i < 10000:
		if n % pl[i] == 0:
			nb += 1
			s = 1
			while n % pl[i] == 0:
				n //= pl[i]
				s = pl[i] * s + 1
			sumdiv *= s
		i += 1
	if n > 1:
		if pow(2, n, n) == 2 and pow(3, n, n) == 3 and (pow(5, n, n) == 5):
			nb += 1
			sumdiv = 0
		elif int(n ** 0.5) ** 2 == n:
			nb += 1
		else:
			nb += 2
			sumdiv = 0
	return (nb % 2, sumdiv % 2)
n = int(input())
l = list(map(int, input().split()))
V = [[0, 0], [0, 0]]
for d in l:
	(i, j) = nbdivsumdiv(d)
	V[i][j] += 1
print(max(V[0][0] + V[0][1], V[0][0] + V[1][0], V[0][1] + V[1][1], V[1][0] + V[1][1]))


def prime(n):
	(f, rs, M) = ([4294967295] * (n + 1 + 31 >> 5), [2], [1 << (i >> 1) for i in range(32)])
	for i in range(3, n + 1, 2):
		if i & 1 and f[i >> 5] & M[i & 31]:
			rs.append(i)
		for j in range(1, len(rs)):
			pi = rs[j] * i
			if pi > n:
				break
			if f[pi >> 5] & M[pi & 31]:
				f[pi >> 5] -= M[pi & 31]
			if i % rs[j] == 0:
				break
	return rs
PS = prime(int(3 * 10 ** 6))

def divsCntSum(n):
	(s, r) = (0, 1)
	for p in PS:
		if n % p == 0:
			c = 0
			while n % p == 0:
				n //= p
				c += 1
			r = r * (p & 1 == 0 or c & 1 == 0)
			s += 1
		if p * p > n:
			break
	if n > 1:
		r = 0
		s += 1
	return (s & 1, r)
ms = [0, 0, 0, 0]
input()
for d in [int(x) for x in input().split(' ')]:
	(dc, ds) = divsCntSum(d)
	ms[dc] += 1
	ms[2 + ds] += 1
print(max(ms))


def sieve(bound):
	arr = [1 for i in range(bound - 2)]
	arr.insert(0, 0)
	arr.insert(0, 0)
	ps = []
	l = len(arr)
	sq = 0
	for (i, val) in enumerate(arr):
		if sq > bound:
			break
		elif val == 1:
			ind = i
			ps.append(i)
			for ind in range(sq, l, i):
				arr[ind] = 0
		sq = sq + 2 * i + 1
	for j in range(i, l):
		if arr[j] == 1:
			ps.append(j)
	return ps
primes = sieve(pow(10, 5))

def sieve_factor(n):
	divs = 0
	if n == 1:
		return 0
	if is_prime(n):
		return 1
	for div in primes:
		check = False
		if n % div == 0:
			divs += 1
			n = n // div
			check = True
		while n % div == 0:
			n = n // div
		if n == 1:
			return divs
		if check:
			sq = int_sqrt(n)
			while sq ** 2 == n:
				n = sq
				sq = int_sqrt(n)
			if is_prime(n):
				return divs + 1
		if pow(div, 3) > n:
			break
	sq = int_sqrt(n)
	while sq ** 2 == n:
		n = sq
		sq = int_sqrt(n)
	if is_prime(n):
		return divs + 1
	if n != 1:
		return divs + 2
	return divs

def is_prime(k):
	small = [2, 3, 5, 7, 11, 13, 17, 19, 23]
	if k in small:
		return True
	if k % 2 == 0:
		return False
	odd = k - 1
	e = 0
	while odd % 2 == 0:
		e += 1
		odd = odd // 2
	for p in small:
		num = pow(p, odd, k)
		check = False
		if num == 1 or num == k - 1:
			continue
		for i in range(e):
			num = pow(num, 2, k)
			if num == k - 1:
				check = True
				break
			if num == 1:
				return False
		if not check and num != 1:
			return False
	return True

def condition(sq, n):
	if sq ** 2 <= n and (sq + 1) ** 2 > n:
		return True
	return False

def int_sqrt(n):
	if n < 4:
		return 1
	guess = n // 2
	while not condition(guess, n):
		guess = (guess + n // guess) // 2
	return guess
n = int(input())
d = list(map(int, input().split()))
data1 = []
data2 = []
for num in d:
	num_divs = 0
	if num % 2 == 0:
		num = num // 2
		num_divs += 1
		while num % 2 == 0:
			num = num // 2
	if int_sqrt(num) ** 2 == num:
		data1.append(1)
	else:
		data1.append(0)
	num_divs += sieve_factor(num)
	data2.append(num_divs % 2)
data1_zeros = 0
for elem in data1:
	if elem == 0:
		data1_zeros += 1
data2_zeros = 0
for elem in data2:
	if elem == 0:
		data2_zeros += 1
print(max(data1_zeros, data2_zeros, n - data1_zeros, n - data2_zeros))


import math
maxprime = 100000
isprime = [True] * maxprime
primelist = []
numprimes = 0
for i in range(2, maxprime):
	if isprime[i]:
		primelist.append(i)
		numprimes += 1
		for j in range(i * i, maxprime, i):
			isprime[j] = False

def isitprime(n):
	for p in primelist[:100]:
		if n == p:
			return True
		if pow(p, n - 1, n) != 1:
			return False
	return True
parity = dict()
parity[1] = [0, 1]

def par(n, i):
	try:
		return parity[n]
	except:
		for j in range(i, numprimes):
			p = primelist[j]
			if n % p == 0:
				curr = n
				e = 1
				while curr % p == 0:
					curr //= p
					e += 1
				subpar = par(curr, j + 1)
				toret = [1 + subpar[0], subpar[1] * (1 if p == 2 else e % 2)]
				parity[n] = toret
				return toret
		subsqrt = int(math.sqrt(n))
		if isitprime(n):
			return [1, 0]
		elif n == subsqrt * subsqrt:
			return [1, 1]
		else:
			return [2, 0]
n = int(input())
d = list(map(int, input().split(' ')))
numeach = [[0, 0], [0, 0]]
for i in d:
	[a, b] = par(i, 0)
	numeach[a % 2][b % 2] += 1
print(max(numeach[0][0] + numeach[0][1], numeach[1][0] + numeach[1][1], numeach[0][0] + numeach[1][0], numeach[0][1] + numeach[1][1]))


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import random
import math

def isPrime(n, k):
	nn = n - 1
	s = 1
	while nn % 2 ** s == 0:
		s += 1
	s -= 1
	d = int(nn // 2 ** s)
	for i in range(k):
		a = random.randint(2, n - 1)
		x = pow(a, d, n)
		if x == 1 or x == n - 1:
			continue
		flag = True
		for r in range(1, s):
			x = pow(x, 2, n)
			if x == 1:
				return False
			if x == n - 1:
				flag = False
				break
		if not flag:
			continue
		return False
	return True
n = int(input())
tab11 = 0
tab10 = 0
tab01 = 0
tab00 = 0
D = input().split()
n = len(D)
for i in range(n):
	tmp = int(D[i])
	somme = 1
	count = 0
	if not tmp & 1:
		count = 1
		tmp = tmp >> 1
		while not tmp & 1:
			tmp = tmp >> 1
	j = 3
	if tmp % j == 0:
		nbenter = 1
		count = count + 1
		tmp = tmp / j
		while tmp % j == 0:
			nbenter += 1
			tmp = tmp / j
		if nbenter & 1:
			somme = 0
	j = 5
	if tmp % j == 0:
		nbenter = 1
		count = count + 1
		tmp = tmp / j
		while tmp % j == 0:
			nbenter += 1
			tmp = tmp / j
		if nbenter & 1:
			somme = 0
	exit100k = 0
	j = 5
	while j * j <= tmp:
		j += 2
		if j * j * j > tmp:
			exit100k = 1
			break
		if tmp % j == 0:
			nbenter = 1
			count = count + 1
			tmp = tmp / j
			while tmp % j == 0:
				nbenter += 1
				tmp = tmp / j
			if nbenter & 1:
				somme = 0
	if exit100k & 1:
		exit100k = math.floor(math.sqrt(tmp))
		if exit100k * exit100k == tmp:
			count += 1
		else:
			somme = 0
			if isPrime(int(tmp), 50):
				count += 1
	elif tmp > 1:
		somme = 0
		count += 1
	if count & 1:
		if somme & 1:
			tab11 += 1
		else:
			tab10 += 1
	elif somme & 1:
		tab01 += 1
	else:
		tab00 += 1
maxi = max(tab11 + tab10, tab11 + tab01, tab00 + tab10, tab00 + tab01)
print(maxi)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import random
import math

def isPrime(n, k):
	nn = n - 1
	s = 1
	while nn % 2 ** s == 0:
		s += 1
	s -= 1
	d = int(nn // 2 ** s)
	for i in range(k):
		a = random.randint(2, n - 1)
		x = pow(a, d, n)
		if x == 1 or x == n - 1:
			continue
		flag = True
		for r in range(1, s):
			x = pow(x, 2, n)
			if x == 1:
				return False
			if x == n - 1:
				flag = False
				break
		if not flag:
			continue
		return False
	return True
n = int(input())
tab11 = 0
tab10 = 0
tab01 = 0
tab00 = 0
D = input().split()
n = len(D)
for i in range(n):
	tmp = int(D[i])
	somme = 1
	count = 0
	if not tmp & 1:
		count = 1
		tmp = tmp >> 1
		while not tmp & 1:
			tmp = tmp >> 1
	j = 3
	if tmp % j == 0:
		nbenter = 1
		count = count + 1
		tmp = tmp / j
		while tmp % j == 0:
			nbenter += 1
			tmp = tmp / j
		if nbenter & 1:
			somme = 0
	j = 5
	if tmp % j == 0:
		nbenter = 1
		count = count + 1
		tmp = tmp / j
		while tmp % j == 0:
			nbenter += 1
			tmp = tmp / j
		if nbenter & 1:
			somme = 0
	exit100k = 0
	j = 5
	while j * j <= tmp:
		j += 2
		if j * j * j > tmp:
			exit100k = 1
			break
		if tmp % j == 0:
			nbenter = 1
			count = count + 1
			tmp = tmp / j
			while tmp % j == 0:
				nbenter += 1
				tmp = tmp / j
			if nbenter & 1:
				somme = 0
	if exit100k & 1:
		exit100k = math.floor(math.sqrt(tmp))
		if exit100k * exit100k == tmp:
			count += 1
		else:
			somme = 0
			if isPrime(int(tmp), 50):
				count += 1
	elif tmp > 1:
		somme = 0
		count += 1
	if count & 1:
		if somme & 1:
			tab11 += 1
		else:
			tab10 += 1
	elif somme & 1:
		tab01 += 1
	else:
		tab00 += 1
maxi = max(tab11 + tab10, tab11 + tab01, tab00 + tab10, tab00 + tab01)
print(maxi)


import random
import math

def isPrime(n, k):
	nn = n - 1
	s = 1
	while nn % 2 ** s == 0:
		s += 1
	s -= 1
	d = int(nn // 2 ** s)
	for i in range(k):
		a = random.randint(2, n - 1)
		x = pow(a, d, n)
		if x == 1 or x == n - 1:
			continue
		flag = True
		for r in range(1, s):
			x = pow(x, 2, n)
			if x == 1:
				return False
			if x == n - 1:
				flag = False
				break
		if not flag:
			continue
		return False
	return True
n = int(input())
tab11 = 0
tab10 = 0
tab01 = 0
tab00 = 0
D = input().split()
n = len(D)
for i in range(n):
	tmp = int(D[i])
	somme = 1
	count = 0
	if not tmp & 1:
		count = 1
		tmp = tmp >> 1
		while not tmp & 1:
			tmp = tmp >> 1
	j = 3
	if tmp % j == 0:
		nbenter = 1
		count = count + 1
		tmp = tmp / j
		while tmp % j == 0:
			nbenter += 1
			tmp = tmp / j
		if nbenter & 1:
			somme = 0
	j = 5
	if tmp % j == 0:
		nbenter = 1
		count = count + 1
		tmp = tmp / j
		while tmp % j == 0:
			nbenter += 1
			tmp = tmp / j
		if nbenter & 1:
			somme = 0
	exit100k = 0
	j = 5
	while j * j <= tmp:
		j += 2
		if j * j * j > tmp:
			exit100k = 1
			break
		if tmp % j == 0:
			nbenter = 1
			count = count + 1
			tmp = tmp / j
			while tmp % j == 0:
				nbenter += 1
				tmp = tmp / j
			if nbenter & 1:
				somme = 0
	if exit100k & 1:
		exit100k = math.floor(math.sqrt(tmp))
		if exit100k * exit100k == tmp:
			count += 1
		else:
			somme = 0
			if isPrime(int(tmp), 50):
				count += 1
	elif tmp > 1:
		somme = 0
		count += 1
	if count & 1:
		if somme & 1:
			tab11 += 1
		else:
			tab10 += 1
	elif somme & 1:
		tab01 += 1
	else:
		tab00 += 1
maxi = max(tab11 + tab10, tab11 + tab01, tab00 + tab10, tab00 + tab01)
print(maxi)


import random
import math

def isPrime(n, k):
	nn = n - 1
	s = 1
	while nn % 2 ** s == 0:
		s += 1
	s -= 1
	d = int(nn // 2 ** s)
	for i in range(k):
		a = random.randint(2, n - 1)
		x = pow(a, d, n)
		if x == 1 or x == n - 1:
			continue
		flag = True
		for r in range(1, s):
			x = pow(x, 2, n)
			if x == 1:
				return False
			if x == n - 1:
				flag = False
				break
		if not flag:
			continue
		return False
	return True
n = int(input())
tab11 = 0
tab10 = 0
tab01 = 0
tab00 = 0
D = input().split()
n = len(D)
for i in range(n):
	tmp = int(D[i])
	somme = 1
	count = 0
	if not tmp & 1:
		count = 1
		tmp = tmp >> 1
		while not tmp & 1:
			tmp = tmp >> 1
	j = 3
	if tmp % j == 0:
		nbenter = 1
		count = count + 1
		tmp = tmp / j
		while tmp % j == 0:
			nbenter += 1
			tmp = tmp / j
		if nbenter & 1:
			somme = 0
	j = 5
	if tmp % j == 0:
		nbenter = 1
		count = count + 1
		tmp = tmp / j
		while tmp % j == 0:
			nbenter += 1
			tmp = tmp / j
		if nbenter & 1:
			somme = 0
	exit100k = 0
	j = 5
	while j * j <= tmp:
		j += 2
		if j * j * j > tmp:
			exit100k = 1
			break
		if tmp % j == 0:
			nbenter = 1
			count = count + 1
			tmp = tmp / j
			while tmp % j == 0:
				nbenter += 1
				tmp = tmp / j
			if nbenter & 1:
				somme = 0
	if exit100k & 1:
		exit100k = math.floor(math.sqrt(tmp))
		if exit100k * exit100k == tmp:
			count += 1
		else:
			somme = 0
			if isPrime(int(tmp), 50):
				count += 1
	elif tmp > 1:
		somme = 0
		count += 1
	if count & 1:
		if somme & 1:
			tab11 += 1
		else:
			tab10 += 1
	elif somme & 1:
		tab01 += 1
	else:
		tab00 += 1
maxi = max(tab11 + tab10, tab11 + tab01, tab00 + tab10, tab00 + tab01)
print(maxi)


import random
import math

def isPrime(n, k):
	nn = n - 1
	s = 1
	while nn % 2 ** s == 0:
		s += 1
	s -= 1
	d = int(nn // 2 ** s)
	for i in range(k):
		a = random.randint(2, n - 1)
		x = pow(a, d, n)
		if x == 1 or x == n - 1:
			continue
		flag = True
		for r in range(1, s):
			x = pow(x, 2, n)
			if x == 1:
				return False
			if x == n - 1:
				flag = False
				break
		if not flag:
			continue
		return False
	return True
n = int(input())
tab11 = 0
tab10 = 0
tab01 = 0
tab00 = 0
D = input().split()
n = len(D)
for i in range(n):
	tmp = int(D[i])
	somme = 1
	count = 0
	if not tmp & 1:
		count = 1
		tmp = tmp >> 1
		while not tmp & 1:
			tmp = tmp >> 1
	j = 3
	if tmp % j == 0:
		nbenter = 1
		count = count + 1
		tmp = tmp / j
		while tmp % j == 0:
			nbenter += 1
			tmp = tmp / j
		if nbenter & 1:
			somme = 0
	j = 5
	if tmp % j == 0:
		nbenter = 1
		count = count + 1
		tmp = tmp / j
		while tmp % j == 0:
			nbenter += 1
			tmp = tmp / j
		if nbenter & 1:
			somme = 0
	exit100k = 0
	j = 5
	while j * j <= tmp:
		j += 2
		if j * j * j > tmp:
			exit100k = 1
			break
		if tmp % j == 0:
			nbenter = 1
			count = count + 1
			tmp = tmp / j
			while tmp % j == 0:
				nbenter += 1
				tmp = tmp / j
			if nbenter & 1:
				somme = 0
	if exit100k & 1:
		exit100k = math.floor(math.sqrt(tmp))
		if exit100k * exit100k == tmp:
			count += 1
		else:
			somme = 0
			if isPrime(int(tmp), 50):
				count += 1
	elif tmp > 1:
		somme = 0
		count += 1
	if count & 1:
		if somme & 1:
			tab11 += 1
		else:
			tab10 += 1
	elif somme & 1:
		tab01 += 1
	else:
		tab00 += 1
maxi = max(tab11 + tab10, tab11 + tab01, tab00 + tab10, tab00 + tab01)
print(maxi)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import sys
import math
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)


import math
import sys
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Primes = []
IsPrime = [True] * 100001
for p in range(2, 100000):
	if not IsPrime[p]:
		continue
	Primes.append(p)
	mult = p * p
	while mult < 100001:
		IsPrime[mult] = False
		mult += p

def GetRidOf2(n):
	while n % 2 == 0:
		n //= 2
	return n

def IsComposite(n, a, s, d):
	if pow(a, d, n) == 1:
		return False
	for r in range(s):
		if pow(a, (1 << r) * d, n) == n - 1:
			return False
	return True

def IsPrime(n):
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for a in witnesses:
		if IsComposite(n, a, s, d):
			return False
	return True

def IsNPowerOfPrime(n):
	if IsPrime(n):
		return True
	sqrt = int(math.sqrt(n))
	if sqrt * sqrt == n and IsPrime(n):
		return True
	return False

def IsNSquare(n):
	sqrt = int(math.sqrt(n))
	return sqrt * sqrt == n

def Factor(n):
	nbFactors = 0
	sumFactors = 0
	if n % 2 == 0:
		nbFactors += 1
		n = GetRidOf2(n)
	if IsNSquare(n):
		sumFactors = 1
		n = int(math.sqrt(n))
	for prime in Primes:
		if n == 1:
			break
		if n % prime != 0:
			continue
		nbFactors += 1
		n //= prime
		while n % prime == 0:
			n //= prime
	if n == 1:
		return (nbFactors, sumFactors)
	if IsNPowerOfPrime(n):
		return (nbFactors + 1, sumFactors)
	return (nbFactors + 2, sumFactors)
result = [[0, 0], [0, 0]]
for n in numbers:
	(nb, s) = Factor(n)
	result[nb % 2][s] += 1
finalResult = result[0][0] + result[0][1]
finalResult = max(finalResult, result[0][0] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[1][0])
finalResult = max(finalResult, result[1][1] + result[0][1])
print(finalResult)