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$.

见题面

见题面