Lines
Consider a positive integer N. Let A, B and C be non-negative integers, such that A+B+C=N. Let there be N marked points on a line with an equal distance between neighboring ones. Draw lines at an angle of 45 degrees through the leftmost A points, draw lines at an angle of 90 degrees through the next B points, and at an angle of 135 degrees – through the last C points. These lines will intersect in some of points.
For clarity look at the image, where N=5, A=1, B=2, C=2. There are 6 points of intersection.
Your task is quite simple – for given N you are to count the sum of quantities of intersection points for all possible triples A, B, C
.
Input
First line of input contains the quantity of tests T (1 ≤ T ≤ 1000).
Each of the next T lines contains an integer N (2 ≤ N ≤ 10^6) – the quantity of points on the line in a current test.
Output
Output T lines of the form “Case #A: B”, where A is the number of test (beginning from 1), B is the sum of quantities of intersection points for given N.