비용이 다른 이진 탐색 (Large)

정렬된 배열에 새 원소 하나를 넣을 자리를 이진 탐색으로 찾으려 한다. 배열의 원소와 새 원소를 비교하면 "크다" 또는 "작다" 중 하나가 답으로 나온다. "크다"는 새 원소를 비교한 원소의 오른쪽에 넣어야 한다는 뜻이고, "작다"는 왼쪽에 넣어야 한다는 뜻이다. 이 문제에서 "같다"는 나오지 않는다.

비교 결과는 서로 어긋나지 않는다. 새 원소가 배열의 어떤 원소보다 크면 그 원소의 왼쪽에 있는 모든 원소보다도 크고, 어떤 원소보다 작으면 그 원소의 오른쪽에 있는 모든 원소보다도 작다. 배열의 길이가 $n$이면 삽입할 자리는 $n+1$가지다.

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

지금까지 나온 답을 보고 다음에 비교할 원소를 정할 수 있다. 최악의 경우에 드는 비용의 합이 가장 작아지는 전략을 골랐을 때, 그 최악의 비용 합을 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개의 줄에는 각 테스트 케이스의 비교 비용 $a_1, a_2, \dots, a_n$이 공백 없이 이어진 숫자열로 주어진다. 배열의 길이 $n$은 이 숫자열의 길이다.

제한

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

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