Lines#99
Consider a positive integer . Let , , and be non-negative integers such that A + B + C = N. Suppose there are marked points on a line with equal spacing between neighboring points. Draw lines at an angle of degrees through the leftmost points, lines at an angle of degrees through the next points, and lines at an angle of degrees through the rightmost points. These lines will intersect at certain points.
For clarity, see the illustration for the case N=5, A=1, B=2, C=2. In this case, there are intersection points.
Your task: For a given , find the sum of the numbers of intersection points over all possible triples (A, B, C).
The first line contains the number of tests (1 \leq T \leq 1000).
Each of the following lines contains a single integer (2 \leq N \leq 10^6), the number of points on the line in the current test.
Output lines, each in the form "Case #: ", where is the test number (starting from ), and is the sum of intersection points for the given .
Example 1