Counting Quadrilaterals#1710
In the 10 \times 10 grid below you can see five different lattice quadrilaterals. (A lattice quadrilateral is a quadrilateral whose vertices have integer coordinates, sides intersect only at vertices, and none of the internal angles can be equal to degrees.) Of course, these are only a few of the millions of lattice quadrilaterals that can be drawn in the 10 \times 10 grid. Given an N \times N grid, your task is to determine the number of different lattice quadrilaterals that can be constructed in that grid.
The input contains at most test cases. Each line contains a single integer (0 < N < 121). The input is terminated by a line where is zero.
For each line of input, output the answer on a separate line. Each output line must contain two integers: the value of from the input, and the number of lattice quadrilaterals for the N \times N grid. It is guaranteed that the answer will fit in a -bit signed integer.
Warning: This problem does not have an alternative to the author's solution. For verifying test cases, you may write a brute-force solution. Thus, you can find all the answers for small grids (up to 22 \times 22) if you run the program for about hours.
Tip: The time limit for this problem is seconds. Pre-calculation may be a better option if you have difficulty finding an efficient solution. In any case, a brute-force method would take about years to run on a GHz Pentium IV computer.
Example 1