Migrated from Lutece 326 How Many Roads?

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

As a director of cities transportation construction, Elfness is given a mission to connect $n$ cities by a lot of roads. Of course, the more roads to be built, the more convenient it would be. But if there are two roads cross each other, traffic accidents may happen. So it means on Elfness's ACM(All Cities' Map), there are no cross roads. And now, Elfness wants to know how many roads can be built at most(Attention: a road won't have to be a segment, it can be a straight line or a ray)?

Input

The first line of input is a single number $T$($T<1000$),means the number of test cases.The $T$ cases followed,each case contain only one line with a single number $n$($0<n\leq 10^8$),the number of cities.

Output

For each test case,you should output one line. First, output Case #C: , $C$ means the number of the test case which is from $1$ to $T$. Then, output an integer indicates the maximal number of roads can be built.

Samples

3
1
2
3

Case #1: 0
Case #2: 1
Case #3: 3

Resources

elfness