Costly Binary Search (Large)

You want to insert one new object into a sorted array, and you find the insertion position by binary search. Comparing the new object with an object of the array answers either "greater" or "less". "Greater" means the new object goes to the right of the compared object, and "less" means it goes to the left. A comparison never answers "equal" in this problem.

The answers never contradict each other. If the new object is greater than some object of the array, it is also greater than every object to the left of that one. If it is less than some object, it is also less than every object to the right of that one. For an array of $n$ elements there are $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.

You may pick the next object to compare after seeing the answers so far. Play a strategy that minimizes the total cost in the worst case, and report that worst-case total cost.

The first line has the number of test cases $T$. Each of the next $T$ lines holds the comparison costs $a_1, a_2, \dots, a_n$ of one test case as a sequence of digits written with no spaces. The length $n$ of the array is the length of that sequence.

Limits

• $1 \le T \le 50$
• Every digit is between 1 and 9.
• There are no spaces between the digits on one line.
• $1 \le n \le 10^6$

For each test case, print one line 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.