14398번 - 피타고라스 수

문제

피타고라스 수 (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보다 작은 자연수이다.

출력

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

제한

힌트