Simon Haples is a somewhat peculiar person. Not quite
hip, not quite square, he is more of a triangular nature: ever
since childhood, he has had an almost unhealthy obsession with
triangles. Because of his discrete nature, Simon’s favorite
kind of triangles are the Pythagorean ones, in which the side
lengths are three positive integers
$a$,
$b$, and
$c$ such that
$a \le b$ and
$a^2 + b^2 = c^2$.
Recently, Simon has discovered the fantastic world of
counting modulo some integer $n$. As you may imagine, he quickly
realizes that there are multitudes of Pythagorean triples to
which he has previously been oblivious! Simon therefore sets
out to find all Pythagorean triples modulo $n$, i.e., all triples of integers
$a$, $b$ and $c$ between $1$ and $n1$ such that $a \le b$ and $a^2 + b^2 \equiv c^2 \pmod{n}$.
As Simon’s best friend, you realize that there is not much
hope in deterring Simon from his crazy plans, so you decide to
help him by computing how many such triples there are, so that
Simon will know when his work is done.
Input
The input consists of a single integer $n$, satisfying $2 \le n \le 500\, 000$.
Output
Output the number of Pythagorean triples modulo $n$.
Sample Input 1 
Sample Output 1 
7

18

Sample Input 2 
Sample Output 2 
15

64
