Submit: 559 Solved: 113

[Submit] [Status] [Web Board] [Creator:]

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)?

The first line of input is a single number T(T < 1000),means the number of test cases.Then T

cases followed, each case contains only one line with a single number n(0 < n ≤ 10^{8}),the number

of cities.

For each test case,you should output one line. First, output “Case #t: ”, t 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.

```
3
1
2
3
```

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