MINST - The Universe Loves Minimum Steps !

Given an array A[i] of N integers. Your task is to make all the integers 0 by performing the following two operations.

Operation-01: You can select K integers arbitrarily from the array where 1 <= K <= N.

Operation-02: From the K-selected integers, you must have to arbitrarily select A and B integers. You have to arbitrarily select A integers and increase all integers by 1 where 0 <= A <= K and you have to arbitrarily select B integers and decrease all integers by 1 where 0 <= B <= K.

You must perform the above two operations to make all the elements of the array to be 0.

In one step, you can perform the above two operations.

Now your job is to find the minimum number of steps needed to make all the elements of the array to be 0.

Input

Input starts with an integer T (≤ 100) , denoting the number of test cases.

Each case contains an integer N (1 <= N <= 100) and then next line N integers follow. Each integer is between -100 to 100 inclusive.

Output

For each case, print the case number and minimum number of steps needed.

Input:
2
3
7 7 7
4
1 -2 1 2

Output:
Case 1: 7
Case 2: 2

Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology


Added by:Alim
Date:2016-04-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own Problem

hide comments
2020-06-28 21:25:49
In each step, you can perform 2 operations:
- add 1 to some of the numbers
- subtract 1 from some of the numbers
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.