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

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

적당한 각의 삼각형이란 이 문제에서 각 중 적어도 하나가 정확히 60도인 삼각형을 가리킨다. 적당한 각의 삼각형은 훨씬 더 잘 알려진 직각삼각형에 비해 흔히 소외감을 느끼지만(이른바 작은 각 콤플렉스), 적당한 각의 삼각형에도 변의 길이에 관한 멋진 공식이 있다:

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

숫자 $N$을 입력받고($1$에서 $200\,000$ 사이), 변의 길이가 $1$에서 $N$ 사이의 정수인 적당한 각의 삼각형이 몇 개인지 출력하여 이 삼각형들의 갈등에 약간의 정의를 실현하는 프로그램을 작성한다.

입력은 $1$개에서 $10\,000$개의 줄로 이루어지며, 각 줄에는 정수 $N$, $1 \leq N \leq 200\,000$이 주어진다.

입력의 각 줄마다 기준을 만족하는 적당한 각의 삼각형의 개수인 정수 하나를 한 줄에 출력한다.