SP209 MAP - The Map

After a new administrative division of Byteland cartographic office works on a new demographic map of the country. Because of technical reasons only a few colors can be used. The map should be colored so that regions with the same or similar population (number of inhabitants) have the same color. For a given color _k_ let **A**(_k_) be the number, such that: - at least half of regions with color _k_ has population not greater than **A**(_k_) - at least half of regions with color _k_ has population not less than **A**(_k_) **A coloring error of a region** is an absolute value of the difference between **A**(_k_) and the region's population. **A cumulative error** is a sum of coloring errors of all regions. We are looking for an optimal coloring of the map (the one with the minimal cumulative error). ### Task Write a program which: - reads the population of regions in Byteland from the standard input, - computes the minimal cumulative error, - writes the result to the standard output.

The number of test cases t is in the first line of input, then t test cases follow separated by an empty line. In the first line of each test case an integer _n_ is written, which is the number of regions in Byteland, _10< n

Your program should write for each test case one integer number equal to a minimal cumulative error, which can be achieved while the map is colored (optimally).