The Pythagorean Theorem

Sanggeun loves triangles, and right triangles most of all.

A right triangle has side lengths that are positive integers $a$, $b$, $c$ with $a \le b$ and $a^2 + b^2 = c^2$.

After learning modular arithmetic, Sanggeun decided to apply it to the Pythagorean theorem.

Given an integer $n$, he wants to count the ordered triples $(a, b, c)$ with $1 \le a, b, c \le n-1$ and $a \le b$ that satisfy

$a^2 + b^2 \equiv c^2 \pmod{n}.$

Write a program that, given $n$, computes the number of such triples $(a, b, c)$.

The first line contains an integer $n$. ($2 \le n \le 500{,}000$)

Print the number of triples $(a, b, c)$ that satisfy the condition.