Dr. Bari is working on some chemical formation. He believes that chemicals and shapes that are regular in shape, are always easy to deal with. But Dr. Khan believes that Dr. Bari is wrong.

To challenge Dr. Bari, Dr. Khan asks him to count the number of intersections of the diagonals of a regular polygon. "I know it is easy to find the number of intersection points made by irregular polygon, but can you find it for regular convex n-gon? To make things easy for you, find only the values for odd n-gon."

Now, your task is simple: help Dr. Bari to find out the desired number.

Input

First line contains a number T (1 ≤ T ≤ 1000), the number of test cases. Each test contains only one odd integer n (1 ≤ n ≤ 2000).

Output

For each case print the case number and the number of intersecting points made by the diagonals of a regular convex n-gon.

Sample

Input

Output

3
1
5
31

Case 1: 0
Case 2: 5
Case 3: 31465

A regular n-gon is a polygon with n sides and all the sides of same size.