Just A Few More Triangles! |
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
Recently, Simon has discovered the fantastic world of counting modulo
some integer 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.
The input consists of a single integer n
Input
The input file contains several test cases, each of them as described below.
Output
For each test case, write to the output, on a line by itself, the number of Pythagorean triples modulo n
Sample Input
7
15
Sample Output
18
64