当前没有测试数据。

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 testcase file contains T denoting the no. of test queries followed by T numbers N, denoting the no. 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