적당한 각의 삼각형 (어려움)

이 문제는 적당한 각의 삼각형(lagomvinklade) 문제의 더 어려운 버전이다.

이 문제에서는 각 중 적어도 하나가 정확히 60도인 삼각형을 적당한 각의 삼각형이라고 부른다. 적당한 각의 삼각형은 훨씬 더 잘 알려진 직각삼각형과 비교해 흔히 소외감을 느낀다(이른바 작은 각 콤플렉스). 적당한 각의 삼각형에도 변의 길이에 관한 멋진 공식이 있는데도 말이다.

$c^2 = a^2 + b^2 - ab$

이 삼각형들의 소동에 조금이나마 공정을 기하기 위해, 수 $N$을 입력받고($1$과 $3000$ 사이), 변의 길이가 $1$부터 $N$까지의 구간에 속하는 정수인 적당한 각의 삼각형이 몇 개인지 출력하는 프로그램을 작성한다.

입력은 정수 $N$ 하나만 포함하는 한 줄로 이루어진다. $1 \leq N \leq 3000$.

조건을 만족하는 적당한 각의 삼각형의 개수를 나타내는 정수 하나를 한 줄에 출력한다.