21032번 - Odd GCD Matching 다국어

문제

Supposed there are N integers A_1..N. A_i can be paired with A_j if GCD(A_i, A_j) is an odd number. 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 an odd number; however, 12 cannot be paired with 8 because GCD(12, 8) = 4 is an even number.

An odd GCD matching of A_1..N is a set of pairs which satisfies the following.

• Each pair contains two integers (i, j) where 1 ≤ i < j ≤ N.
• Each integer i only appears at most once in the set.
• If (i, j) is in the set, then Ai must be able to be paired with A_j.

Given A_1..N, your task is to find the size of a maximum odd GCD matching of A_1..N. An odd GCD matching is maximum if and only if there are no other odd GCD matching which has more pairs than it.

For example, let A_1..5 = {6, 8, 9, 12, 13}. The size of a maximum odd GCD matching in this example is 2; one such example is {(1, 3),(2, 5)} which corresponds to the pairs (A₁ = 6 with A₃ = 9) and (A₂ = 8 with A₅ = 13). Note that {(1, 3)} with the size of 1 is also a valid odd GCD matching, but it is not a maximum one. On the other hand, {(2, 4)} is not a valid odd GCD matching as A₂ = 8 cannot be paired with A₄ = 12 in this example.

입력

Input begins with a line containing an integer: N (1 ≤ N ≤ 20 000) representing the size of A. The next line contains N integers: A_i (1 ≤ A_i ≤ 10⁶) representing the array A.

출력

Output in a line an integer representing the size of a maximum odd GCD matching of A_1..N.

제한

힌트