Pythagorean Triples

Time limit2sMemory limit512 MB

Summary

Given N stick lengths, pair them into as many disjoint pairs as possible so each pair forms the legs of a primitive Pythagorean triple.

Level: Medium7 of 10
Topics: Graph, Math, Number theory, Backtracking
Solved: No attempts yet

Problem

A Pythagorean triple $(a, b, c)$ is a triple of numbers that satisfies all of the following conditions.

$a$ , $b$ , and $c$ are integers.
$a^2 + b^2 = c^2$
The greatest common divisor of $a$ and $b$ is 1.

Youngsun has $N$ wooden sticks and wants to build as many toys shaped like right triangles as possible. The side lengths $(a, b, c)$ of each toy must form a Pythagorean triple. The two sides $a$ and $b$ are made of wooden sticks, and the remaining side $c$ is made of an iron stick. A wooden stick used in one toy cannot be used again in another toy. Youngsun has so many iron sticks that they never run out.

Find the maximum number of toys Youngsun can build.

Input

The first line contains the number of wooden sticks $N$ ( $1 \le N \le 200$ ).

The second line contains the lengths of the $N$ wooden sticks, separated by spaces. Each length is a positive integer less than 1,000,000.

Output

Print the maximum number of toys that can be built on the first line.

Examples3

Example 1
Input
```
9
3 4 4 3 11 5 12 9 4
```
Expected output
```
3
```
Example 2
Input
```
4
20 21 3021 220
```
Expected output
```
2
```
Example 3
Input
```
5
28 195 1035 21412 37995
```
Expected output
```
2
```