JGTLE - Jalil Got TLE

no tags 

Ananta Jalil is a multi talented person. He can make any task possible which is impossible to others. Recently he has learned programming basic. In a problem, he submitted the following solution:

#include <stdio.h>

int main()
{
    int t;
    scanf("%d", &t);
    for(int tc = 1; tc <= t; ++tc) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        long long result = 0;
        for(int i = 1; i <= a; ++i) {
            for(int j = 1; j <= b; ++j) {
                for(int k = 1; k <= c; ++k) {
                    result += j * k;
                }
            }
        }
        printf("Case %d: %lld\n", tc, result);
    }
    return 0;
}

But he got TLE (Time Limit Exceeded) as he is novice in programming. That’s why his solution was not efficient. So you are here to write an optimized solution for Jalil which will give the same output.

Input

The first line of input will contain a positive integer T denoting the number of test cases.

In each test case, there will be 3 positive integers a, b and c.

Constraints

  • T <= 1000
  • a <= 30
  • b <= 100000
  • c <= 10000

Output

For each test case, print the output as same as the above program.

Example

Input

3
1 4 3
3 4 2
143 342 777

Output

Case 1: 60
Case 2: 90
Case 3: 2535110464887

hide comments
stcsteven: 2018-01-03 16:26:51

Your "a" value does not fit in the constraint given :(

Arkadiusz Bulski: 2017-12-31 17:48:51

I bet there is an analytica solution to it, so of course it can be done in zero time.

hanstan: 2017-12-30 15:11:09

Nailed it 0.00s


Added by:Sarwar
Date:2017-12-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All