Given some set of points on a circle, you connect every pair of them with a line, find the maximum number of sections do these lines cut the circle into?

Input

First line for each test case file contains T denoting the number of test queries followed by T numbers N, denoting the number of point on a circle.

Constraints

1 ≤ T ≤ 100000 (10⁵)

1 ≤ N ≤ 100000 (10⁵)

Note: Use fast I/O methods.

Output

For each test query, output the result in given format. As the result can be large answer the result modulus 1000000007 (10⁹ +7).

Case <test_query_i>: <max_section_circle_cuts_into>

Example

Input:
3
1
2
6

Output:
Case 1: 1
Case 2: 2
Case 3: 31