벽화

Thanh은 N개의 구역으로 이루어진 벽에 멋진 벽화를 그리고 싶어 한다. 벽의 각 구역에는 아름다움 점수가 있으며, 이는 그 구역을 칠했을 때 얼마나 아름답게 보일지를 나타낸다. 안타깝게도 최근 홍수로 벽이 무너지기 시작했으므로, 그는 서둘러 작업해야 한다!

매일 시작할 때 Thanh은 벽의 구역 하나를 칠한다. 첫날에는 원하는 아무 구역이나 자유롭게 칠할 수 있다. 그다음 날부터는 벽화를 여러 부분으로 나누고 싶지 않으므로, 이미 칠한 구역과 인접한 새로운 구역을 칠해야 한다.

매일 끝날 때 벽의 구역 하나가 파괴된다. 파괴되는 구역은 항상 다른 구역 하나에만 인접하면서 칠해지지 않은 벽 구역이다(Thanh은 방수 페인트를 사용하므로 칠해진 구역은 파괴될 수 없다).

Thanh의 벽화가 갖는 총 아름다움은 그가 칠한 구역들의 아름다움 점수의 합과 같다. Thanh은 벽이 어떤 방식으로 파괴되더라도 여전히 적어도 B의 총 아름다움을 달성할 수 있음을 보장하고 싶어 한다. 그가 이를 보장할 수 있는 B의 최댓값은 얼마인가?

제한

1 ≤ T ≤ 100. 테스트 세트당 시간 제한: 20초. 메모리 제한: 1 GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

2 ≤ N ≤ 100.

큰 데이터 세트 (테스트 세트 2 - 비공개)

정확히 1개의 케이스에서는 N = 5 × $10^{6}$이고, 나머지 T - 1개의 케이스에서는 2 ≤ N ≤ 100.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 N이 적힌 줄로 시작한다. 그다음 줄에는 0부터 9까지의 숫자로 이루어진 길이 N의 문자열이 주어진다. i번째 숫자는 벽의 i번째 구역의 아름다움 점수를 나타낸다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 위에서 설명한 대로 Thanh이 달성할 수 있다고 보장할 수 있는 아름다움 점수의 최댓값이다.

첫 번째 예제 케이스에서 Thanh은 벽이 어떤 방식으로 파괴되더라도 총 아름다움 6을 얻을 수 있다. 첫날에는 아름다움 점수가 3인 벽의 두 구역 중 어느 쪽이든 칠할 수 있다. 그날이 끝날 때 1st 구역이나 4th 구역 중 하나가 파괴되지만, 어느 쪽인지는 중요하지 않다. 둘째 날에는 아름다움 점수가 3인 나머지 구역을 칠할 수 있다.

두 번째 예제 케이스에서 Thanh은 가장 왼쪽의 벽 구역(아름다움 점수가 9인 구역)을 칠하여 총 아름다움 14을 얻을 수 있다. 가장 왼쪽 구역은 칠해져 있으므로, 파괴될 수 있는 유일한 벽 구역은 가장 오른쪽 구역이다. 둘째 날에는 왼쪽에서 둘째인, 아름다움 점수가 5인 구역을 칠할 수 있다. 그러면 오른쪽에 남아 있는 마지막 미도색 벽 구역이 파괴된다. 둘째 날에 Thanh은 벽의 셋째 구역(아름다움 점수가 8인 구역)을 칠하도록 선택할 수 없다는 점에 유의한다. 그 구역은 칠해진 어떤 구역과도 인접하지 않기 때문이다.

세 번째 예제 케이스에서 Thanh은 총 아름다움 7을 얻을 수 있다. 그는 가운데 구역(아름다움 점수가 1인 구역)을 칠하는 것으로 시작한다. 그날이 끝날 때 어느 구역이 파괴되든, 둘째 날이 시작할 때 남은 벽을 칠할 수 있다.