Problem D
Allar mátaðar pýþagorískar

Þú færð gefna tölu $n$ og átt að skoða Pýþagorasarþrenndir mátaðar við $n$. Það þýðir að við séum að skoða fjölda þrennda $(a, b, c)$ með $0 < a, b, c < n$ sem uppfylla $a^2 + b^2 = c^2 \pmod{n}$ og $a \leq b$.

Til dæmis í fyrsta sýniinntaki eru lausnirnar $(1, 2, 1)$, $(1, 2, 3)$, $(2, 2, 2)$, $(2, 3, 1)$ og $(2, 3, 3)$.

Inntak

Fyrsta og eina lína inntaksins gefur jákvæða heiltölu $n$, gildið sem á að máta við. Það mun uppfylla $1 \leq n \leq 2 \cdot 10^5$.

Úttak

Prentið fjölda Pýþagórasaþrennda þegar mátað er við $n$.

4

5

7

18

15

64