Round Dollar

Description

In 2019, the Canadian Government did away with all coins of value less than a dollar. To pay for purchases, the amount is rounded up or down to the nearest dollar amount. The rules for rounding are as follows.

• A purchase less than a dollar (e.g., 27 cents) rounds up to a dollar (e.g., $1.00).
• For a purchase a dollar or greater, if the dollar amount is even (e.g., $2, $4, $6, etc.), if the cents amount is 50 cents or greater, it rounds up. E.g., $8.50 rounds up to $9.00. Otherwise, it rounds down.
• For a purchase a dollar or greater, if the dollar amount is odd (e.g., $1, $3, $5, etc.), if the cents amount is 51 cents or greater, it rounds up. Otherwise, it rounds down. E.g., $7.50 rounds down to $7.00.

The Government takes in the monies from rounding up and down. The merchants only get the actual purchase amount. They also decreed that the rounding happens even if you use a credit or debit card!

Needless to say, many people were quite upset with the system. A most unlucky person making twenty purchases in a day could end up paying a lot extra due to the rounding up in each case! (For instance, imagine each purchase was $2.50. they'd pay $10.00 more, in all. And if each of the twenty purchases were $0.01, they'd pay $19.80 more!) Of course, if you were extremely lucky, you might have saved as much as $10.00 during the day due to rounding down of each of twenty purchases the maximum possible 50 cents each.

In 2020, Canada went “cashless”. All purchases are now made via your Canadian Cash Card, a government issued debit card. To appease those people who felt unlucky and that they usually lost money to rounding up, the Government allows you to “bracket” your purchases during the day, and to then round up or down to the dollar based on the sum of the purchases in the bracket. (This treats all the purchases in a bracket like a single purchase.) So, if you like more to gamble, you leave each individual purchase in its own “bracket”, to be rounded up or down. If you like to play it safe, you have all your daily purchases in one bracket. That way, the most you could lose on a round up in a day is 50 cents.

But the Government did not account for computer scientists! They let you bracket your daily purchases however you want. And, if you are clever, you can always figure out how to bracket to save you the most money!

Purchases during the day are sequential by time. You are only allowed to bracket together a sequence of purchases. So you cannot put the first and last purchases of the day into a bracket, and all the others into a second bracket.

Input

The input starts with a single integer t, the number of trial cases. The number of trials will be between 1 and 200, inclusive. Each trial begins with a single integer n, the number of purchases for that day. The number of purchases will be between 1 and 20, inclusive. Then n floats follow (each with two digits to the right of the decimal for the cents), which report the sequence of purchases for the day.

Sample Input

4
1
0.47
3
1.50 1.50 1.50
3
2.50 2.50 2.50
3
2.50 2.50 1.50

Output

For each trial, print out on a separate line how much you paid in rounding for the day's purchases with an optimal bracketing. A negative indicates that you saved that money.

Sample Output

0.53
-1.50
-0.50
-0.5