시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 99 6 5 22.727%

문제

피타고라스 수 (a, b, c)는 다음과 같은 조건을 만족하는 세 쌍이다.

  • a, b, c는 정수이다.
  • a^2 + b^2 = c^2
  • a와 b의 최대 공약수는 1이다.

영선이는 나무 막대 N개를 가지고 있다. 영선이는 직각 삼각형 모양의 장난감을 최대한 많이 만드려고 한다. 이때, 장난감의 두 변 a와 b는 나무 막대를 이용해야 하며, 한 변 c는 쇠 막대를 이용해야 한다. 장난감을 만드는데 사용한 나무 막대는 다른 장난감을 만들 때 또 사용할 수 없다. 영선이는 쇠 막대를 매우 많이 가지고 있기 때문에, 부족할 일은 없다.

입력

첫째 줄에 나무 막대의 개수 N (1 ≤ N ≤ 200)이 주어진다.

둘째 줄에는 나무 막대의 길이가 주어진다. 길이는 1,000,000보다 작은 자연수이다.

출력

첫째 줄에 만들 수 있는 장난감의 최대 개수를 출력한다.

예제 입력 1

9
3 4 4 3 11 5 12 9 4

예제 출력 1

3

예제 입력 2

4
20 21 3021 220

예제 출력 2

2

예제 입력 3

5
28 195 1035 21412 37995

예제 출력 3

2

출처