Start

2020-03-31 12:30 CEST

CNG-mästerskapen 2020

End

2020-03-31 14:00 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -248 days 11:13:36

Time elapsed

1:30:00

Time remaining

0:00:00

Problem J
Lagomvinklade trianglar (svår)

Detta är en svårare version av problemet Lagomvinklade trianglar (lagomvinklade).

En lagomvinklad triangel är vad vi i denna uppgift kallar en triangel där minst en av vinklarna är exakt 60 grader. De lagomvinklade trianglarna känner sig ofta förbisedda jämfört med de mycket mer kända rätvinkliga trianglarna (så kallat mindervinkelkomplex), trots att de lagomvinklade också har en snygg formel för sina sidlängder:

\begin{equation*} c^2 = a^2 + b^2 - ab \end{equation*}

Skriv ett program som skipar lite rättvisa i detta triangeldrama genom att fråga efter ett tal $N$ (mellan $1$ och $3000$) och sedan skriva ut hur många lagomvinklade trianglar det finns vars sidor är heltal i intervallet $1$ till $N$.

Input

Indatan består av en rad, innehållandes endast heltalet $N$, $1 \leq N \leq 3000$.

Output

Skriv ut en rad med ett enda heltal; antalet lagomvinklade trianglar som uppfyller kriteriet.

Sample Input 1 Sample Output 1
25
35
Sample Input 2 Sample Output 2
70
112