ke1vin is a smart but poor boy. Now he study in National Taiwan University(NTU), one of the best universities in Taiwan. To save money, he rarely eats at anywhere other than the 7-11s in NTU, since there are discounts for students.
One day he found that the method of discount calculation is special!
The method is as follow:
Suppose all the goods you buy cost x dollars then you should pay x - floor(x*0.1+0.5) (That is, 10% discount. If one decimal place not larger than 5, round it down, and otherwise round it up)
(floor(x) is the largest integer which is not larger than x)
For example, if x = 15, you have to pay 13 dollars. If x = 14, you have to pay 13 dollars, too.
After brief investigation on the method of discount calculation, Pen1vin found that sometimes he could save more money by dividing all goods he bought into several group, and paying them separately.
After discovering the fact, he wants to know the lowest cost he should pay for some particular buying. Although he is very smart, he is busy doing internship. Can you write a program to help him?
The first line has an integer T as the number of test cases.
Then there are another T line, one line for each test case. Each test case starts by a number n, which means there are n goods.(1<=n<=514) Then following n numbers mean the cost of every goods.(every number are positive integer and not larger than 500)
T<=127
For each test case, print an integer in one line represent the least number of dollars ke1vin have to pay.
2 2 5 5 1 10
8 9
Migrated from old NTUJ.
dreamoon
| No. | Testdata Range | Score |
|---|