Costly Binary Search (Small)

You are implementing binary search. There is a sorted array of $n$ objects and one new object that you want to insert into it. To find the insertion position you compare the new object with objects of the array. A comparison answers either greater, meaning the new object belongs to the right of the compared object, or less, meaning it belongs to the left. In this problem a comparison never answers equal. When the new object is greater than some object of the array, it is also greater than every object to the left of that object, and when it is less than some object, it is also less than every object to the right of that object. So an array of $n$ elements has $n+1$ possible insertion positions.

Comparisons do not all cost the same. Comparing the new object with the $i$-th object of the array costs $a_i$, an integer between 1 and 9 inclusive.

Assume you follow a strategy that minimizes the total cost in the worst case. Find that worst case total cost.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains one string of digits that gives the comparison costs $a_1, a_2, \ldots, a_n$ of one test case in order. The length of that string is the size $n$ of the array.

Constraints

• $1 \le T \le 50$
• Every digit is between 1 and 9 inclusive.
• A line contains no spaces.
• $1 \le n \le 10^4$

For each test case print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the worst case total cost of the binary search.