CIRCLEDIV - Euler Puzzle


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 (105)

1 ≤ N ≤ 100000 (105)

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 (109 +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

hide comments
tarun_28: 2020-09-02 09:19:12

No optimization required for PYPY users, just use fast I/O

sanchit_aga: 2019-01-07 13:59:37

Good question. Learnt a new formula.

pranjulpal18: 2019-01-03 16:15:01

Take help of https://en.m.wikipedia.org/wiki/Dividing_a_circle_into_areas
But in this formula n^3 may be greater than 1000000007 and (n^3 % 1000000007)/24 may be not equal to (n^3 / 24)%1000000007

i_love_priya: 2018-11-11 23:12:04

The answer should be the modulus of 10^9+7 .
Be careful
This **** cost me 20 minutes


Added by:ad
Date:2018-10-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:3b1b