Lab Objective

The purpose of this programming assignment is to practice using array.

Background

The world-known gangster Vito Deadstone is moving to New York. He has a very big family there, all of them

living in Lamafia Avenue. Since he will visit all his relatives very often, he is trying to find a house close to

them.

Problem

Vito wants to

minimize the total distance to all of his relatives

and has blackmailed you to write a

program to solve his problem.

Input

The input consists of several test cases. The first line contains the number of test cases. For each test case

you will be given the integer number of relatives

r

( 0 < r < 500) and the street numbers (also integers)

s1

,

s2

, ...,

si

, ...,

sr

where they live ( 0 <

si

< 30000 ). Note that several relatives could live in the same

street number, and Vito can choose to live with one of his relatives.

Output

For each test case your program must print the

minimal sum of distances from the optimal Vito's house

to each one of his relatives

. The distance between two street numbers

si

and

sj

is

d_ij= |si

-

sj|

.

Sample run

Input the number of test cases: 2

Test case 1 input the number of relatives: 2

Test case 1 input the street numbers: 2 4

The minimun total distance is: 2

Test case 2 input the number of relatives: 3

Test case 2 input the street numbers: 4 2 6

The minimun total distance is: 4

Done with all test cases.

Press any key to continue

In the above sample run, a user first input the number of test cases. For each test case, the user enters the

number of relatives, then enters the street numbers where the relatives live. Once your program takes the

input data, it finds

the optimal house number that minimize the total distance to all the relatives

.

Hints

The correct design should be to try every possible number between the smallest street number and

the largest street number for each test case. For example, consider there are 10 relatives living in street

numbers 2, 12, 23, 10, 3, 40, 20, 19, 4, 10. You may try every street number from 2, 3, 4, up to 40, using

a loop, and for each try, calculate the total sum of distance, and then return the smallest distance sum.

Here is another sample run:

Input the number of test cases: 1

Test case 1 input the number of relatives: 10

Test case 1 input the street numbers: 2 12 23 10 3 40 20 19 4 10

The minimun total distance is: 85

Done with all test cases.

Press any key to continue