Solve the programming task below in a Python markdown code block.
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$.