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(\mathrm{mod}n)$ og $a\le 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\le n\le 2\cdot {10}^5$.

Úttak

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

4

5

7

18

15

64