Problem D
All Modulo Pythagorean

You are given a value $n$ and should investigate Pythagorean triples modulo $n$. This means we are considering triples $(a,b,c)$ where $0<a,b,c<n$ that satisfy $a^2+b^2=c^2(\mathrm{mod}n)$ and $a\le b$.

For example in the first sample the solutions are $(1,2,1)$, $(1,2,3)$, $(2,2,2)$, $(2,3,1)$ and $(2,3,3)$.

Input

The first and only line of input contains a positive integer $n$, the modulo we are considering. It will satisfy $1\le n\le 2\cdot {10}^5$.

Output

Print the number of Pythagorean triples modulo $n$.

4

5

7

18

15

64