Lines

prb99 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

Specifications

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⁶) – 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.

Problem information

Time Limit: 10 seconds
Memory Limit: 64 MB
Balls for the passed test: 10
Complexity: 63% 3/8

Example

Example input

Example output

Case #1: 3
Case #2: 13
Case #3: 91

← Longest chain

Problems

Pareto domination →