홀수 GCD 매칭

N개의 정수 $A_1, \ldots, A_N$이 있다. $\gcd(A_i, A_j)$가 홀수이면 $A_i$와 $A_j$를 짝지을 수 있다. $\gcd(a, b)$는 $a$와 $b$의 최대공약수이다. 예를 들어 $\gcd(6, 9) = 3$이 홀수이므로 6과 9는 짝지을 수 있지만, $\gcd(12, 8) = 4$가 짝수이므로 12와 8은 짝지을 수 없다.

$A_1, \ldots, A_N$의 홀수 GCD 매칭이란 다음 조건을 만족하는 짝의 집합이다.

• 각 짝은 $1 \le i < j \le N$인 두 정수 $(i, j)$로 이루어진다.
• 각 정수 $i$는 집합에 많아야 한 번 등장한다.
• $(i, j)$가 집합에 속하면 $A_i$와 $A_j$를 짝지을 수 있어야 한다.

$A_1, \ldots, A_N$이 주어질 때, $A_1, \ldots, A_N$의 최대 홀수 GCD 매칭의 크기를 구하라. 어떤 홀수 GCD 매칭보다 짝의 수가 많은 홀수 GCD 매칭이 존재하지 않으면 그 매칭은 최대이다.

예를 들어 $A_1, \ldots, A_5 = \{6, 8, 9, 12, 13\}$이라 하자. 이 예에서 최대 홀수 GCD 매칭의 크기는 2이며, 그중 하나는 $\{(1, 3), (2, 5)\}$로 $(A_1 = 6$과 $A_3 = 9)$, $(A_2 = 8$과 $A_5 = 13)$을 짝지은 것이다. 크기가 1인 $\{(1, 3)\}$도 올바른 홀수 GCD 매칭이지만 최대는 아니다. 한편 $\{(2, 4)\}$는 이 예에서 $A_2 = 8$과 $A_4 = 12$를 짝지을 수 없으므로 올바른 홀수 GCD 매칭이 아니다.

첫 줄에 $A$의 크기를 나타내는 정수 $N$이 주어진다. ($1 \le N \le 20\,000$) 다음 줄에 배열 $A$를 나타내는 $N$개의 정수 $A_i$가 주어진다. ($1 \le A_i \le 10^6$)

$A_1, \ldots, A_N$의 최대 홀수 GCD 매칭의 크기를 한 줄에 출력한다.