Migrated from Lutece 304 I'm Hungry

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

The canteen in UESTC is a crazy place. Every day, thousands of people are rushing to the canteen after class. But there is a long line before the each window always, which makes people disappoint and angry.

Today, LY will meet a very important person, so he wants to finish the lunch early. Now he is very anxious and he wants to know how much time he have to wait if those people behind him would finish the queuing as soon as possible.

What's more, there is an interesting phenomenon in the canteen. If two people are a pair of lovers, they always stand together and will choose the same food, so they cost less time. Through the LY’s experience, he knows a pair of lovers (two people together) will cost $40$ seconds constantly, but for a single person, his/her time to cost is variable. LY doesn't know how many pairs of lovers in the line and just knows the time each person will cost separately. He just wants to eat meal early. Can you help him to count the possible minimum time LY will wait before he choosing food? When you count the time, you can arbitrarily assume two adjacent people is a pair of lovers.

Input

The first line of the input contains one integer $T$($T\leq 20$), which indicate the number of test cases.

In each test case, the first line contains an integer $N$($2\leq N\leq 100000$), indicating the number of people before LY.

Following one line contains $N$ integer, the $i_{th}$ integer $a_i$ represents the time the $i_{th}$ people will cost ($1\leq a_i\leq 60$).

Output

For each test case, output one line.First, output Case #C: , where $C$ is the number of test case, from $1$ to $T$. Then output one integer indicating the answer, that is the minimum time LY will wait possibly.

Samples

2
4
12 25 20 10
6
20 7 55 10 29 36

Case #1: 62
Case #2: 107

Resources

BlinKer