비용이 드는 이진 탐색 (Small)

이진 탐색을 직접 구현하려고 한다. 정렬된 원소 $n$개짜리 배열이 있고, 여기에 새 원소 하나를 끼워 넣어야 한다. 삽입 위치를 찾으려면 새 원소를 배열의 원소와 비교한다. 비교 결과는 크다 또는 작다 둘 중 하나다. 크다는 새 원소를 비교한 원소의 오른쪽에 넣어야 한다는 뜻이고, 작다는 왼쪽에 넣어야 한다는 뜻이다. 이 문제에서 비교 결과가 같다로 나오는 경우는 없다. 새 원소가 배열의 어떤 원소보다 크면 그 원소의 왼쪽에 있는 모든 원소보다도 크고, 어떤 원소보다 작으면 그 원소의 오른쪽에 있는 모든 원소보다도 작다. 그래서 원소가 $n$개인 배열에서 삽입 위치는 $n+1$가지다.

비교 비용은 위치마다 다르다. 새 원소를 배열의 $i$번째 원소와 비교하는 비용은 $a_i$이고, 1 이상 9 이하의 정수다.

최악의 경우에 드는 총비용이 가장 작아지는 전략을 따른다고 하자. 그때 최악의 경우 총비용을 구하여라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 다음 $T$개의 줄에는 테스트 케이스마다 비교 비용 $a_1, a_2, \ldots, a_n$을 순서대로 이어 붙인 숫자 문자열이 한 줄에 하나씩 주어진다. 이 문자열의 길이가 배열의 크기 $n$이다.

제한

• $1 \le T \le 50$
• 모든 숫자는 1 이상 9 이하이다.
• 한 줄 안에 공백은 없다.
• $1 \le n \le 10^4$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 최악의 경우 이진 탐색에 드는 총비용이다.