피타고라스의 정리

상근이는 삼각형을, 그중에서도 직각삼각형을 매우 좋아한다.

직각삼각형은 세 변의 길이가 양의 정수 $a$, $b$, $c$이고 $a \le b$이며 $a^2 + b^2 = c^2$을 만족하는 삼각형이다.

나머지 연산을 배운 상근이는 피타고라스의 정리에 나머지 연산을 적용해 보기로 했다.

정수 $n$이 주어질 때, $1 \le a, b, c \le n-1$이고 $a \le b$이며

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

을 만족하는 순서쌍 $(a, b, c)$의 개수를 세려고 한다.

$n$이 주어졌을 때, 조건을 만족하는 $(a, b, c)$의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 정수 $n$이 주어진다. ($2 \le n \le 500{,}000$)

첫째 줄에 조건을 만족하는 순서쌍 $(a, b, c)$의 개수를 출력한다.