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

• 1 \le t \le 100
• 1 \le n \le 10^5
• 1 \le p_i \le 10^9
• the sum of all n values is at most 10^5

Example

Input:

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

Output:

35
20
95