Odd GCD Matching

There are $N$ integers $A_1, \ldots, A_N$. $A_i$ can be paired with $A_j$ if $\gcd(A_i, A_j)$ is odd. $\gcd(a, b)$ is the greatest common divisor of $a$ and $b$. For example, 6 can be paired with 9 because $\gcd(6, 9) = 3$ is odd; however, 12 cannot be paired with 8 because $\gcd(12, 8) = 4$ is even.

An odd GCD matching of $A_1, \ldots, A_N$ is a set of pairs satisfying the following.

• Each pair consists of two integers $(i, j)$ with $1 \le i < j \le N$.
• Each integer $i$ appears at most once in the set.
• If $(i, j)$ is in the set, then $A_i$ can be paired with $A_j$.

Given $A_1, \ldots, A_N$, find the size of a maximum odd GCD matching of $A_1, \ldots, A_N$. An odd GCD matching is maximum if and only if no other odd GCD matching has more pairs than it.

For example, let $A_1, \ldots, A_5 = \{6, 8, 9, 12, 13\}$. The size of a maximum odd GCD matching in this example is 2; one such matching is $\{(1, 3), (2, 5)\}$, which pairs $(A_1 = 6$ with $A_3 = 9)$ and $(A_2 = 8$ with $A_5 = 13)$. Note that $\{(1, 3)\}$ with size 1 is also a valid odd GCD matching, but it is not maximum. On the other hand, $\{(2, 4)\}$ is not a valid odd GCD matching because $A_2 = 8$ cannot be paired with $A_4 = 12$ in this example.

The first line contains an integer $N$, the size of $A$. ($1 \le N \le 20\,000$) The next line contains $N$ integers $A_i$, the array $A$. ($1 \le A_i \le 10^6$)

Output in one line an integer, the size of a maximum odd GCD matching of $A_1, \ldots, A_N$.