Code Submission Evaluation System Login

CSES - HIIT Open 2016

HIIT Open 2016

Contest start:2016-05-28 11:00:00
Contest end:2016-05-28 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


Cent saving

Time limit:1.00 s
Memory limit:256 MB

You want to buy $n$ items from a shop. You can visit the shop several times and you don't have to buy all the items together.

The prices for the items are given in cents. When you are at the cashier, the total price for the items will be rounded to the nearest multiple of 5. This may allow you to save money by visiting the shop several times and grouping the items cleverly.

For example, if you want to buy three items with prices 11, 32 and 56 cents, you can visit the shop twice: first buy the 32 cent item (for 30 cents) and then buy the 11 and 56 cent items (for 65 cents). Now the price for all the items is only 95 cents.

You are given the prices for the items and your task is to find out the lowest possible total price for the items.

Input

The first input line contains an integer $t$: the number of test cases. After this, the test cases are described as follows.

The first line contains an integer $n$: the number of items. The second line contains $n$ integers $p_1,p_2,\ldots,p_n$: the price for each item.

Output

For each test case, output the lowest total price for the items.

Constraints
Example

Input:
3
2
18 19
4
5 5 5 5
3
11 32 56


Output:
35
20
95