Description
Speedcell and Shoutmon love triangles very much.One day,they are playing a game named “Triangle Counting”.
In this game,Speedcell draws a round,and draws N points on the circumference of the round evenly,and marks them as 1,2,...,N.
Then Speedcell connects these points using the following rules:
Step 1: Connect the first point with the third point,and connect the third point with the 5th point,...,connect the ith point with the
(i+2)th point(cycling when needed)......It can’t be stopped until we get back to the first point.
Step 2: If there exists some points which don’t be connected still,choose one of them(if marked “i”),and connect it with the
(i+2)th point,then the (i+4)th point as Step1.......If we get back to the ith point,Step 2 will be stopped.
Step 3: Connect all the points as the order 1,2,...,N,1.
Now Speedcell wants to let Shoutmon count the number of triangles on the figure.
Input
The first line of input contains T(T ≤ 1000), indicating the number of cases.
Then T lines follow. Each line an integer N(1 ≤ N ≤ 1000), indicating the number of points.
Output
Each case a line, and output the case number first, then a single integer, indicating the number of triangles.
The answer should be moduloed by 20121111.
Sample Input
3 1 4 6
Sample Output
Case #1: 0 Case #2: 8 Case #3: 32
学了新的数学姿势。
乍一看是找规律，的确，但规律比较特别，在N <= 7 时出现得三角形个数为无规律态。
当大于>7时，规律为 n * 5 ；