Counting Quadrilaterals
In the 10x10 grid below you can see five different lattice quadrilaterals. (A lattice quadrilateral is a quadrilateral whose vertices have integer coordinates. A quadrilateral is a polygon with four sides and is not self intersecting. None of the internal angles of a Quadrilateral can be equal to 180 degree) Of course these are only a few lattice quadrilaterals of the millions that can be drawn in this 10x10 grid. Given an (NxN) grid your job is to count the number of different lattice quadrilaterals in that grid.
Input
The input file contains at most 150 sets of inputs. Each line contains an integer N (0 < N < 121). Input is terminated by a line where the value of N is zero.
Output
For each line of input produce one line of output. This line contains two integers. First integer is the input number N and the second integer denotes the number of quadrilaterals in an (NxN) grid. It is guaranteed that the second integer will fit in a 64-bit signed integer.
Warning: This problem has no alternate solution so can have mistakes. Actually a brute force solution is written to verify the answers. But that could only verify answers up to (22x22) grid after running for 14 hours.
Tips: The time limit of this problem is 2 seconds and has only specific amount of judge input. So pre-calculation can be a better option if a very efficient solution is hard to find. But of course the most obvious brute force method can take around 200 years to complete in a 1.8 Ghz Pentium IV machine.