무한 팬케이크 하우스

무한 팬케이크 하우스에는 팬케이크가 유한하게만 있지만, 그것을 먹고 싶어 하는 손님은 무한히 많다! 식당이 아침 식사를 위해 문을 열 때, 무한히 많은 손님 중 정확히 D명의 접시는 비어 있지 않으며, 이들 중 i번째 손님의 접시에는 팬케이크가 $P_{i}$개 있다. 나머지 모든 손님의 접시는 비어 있다.

보통은 매분, 접시가 비어 있지 않은 모든 손님이 자신의 접시에서 팬케이크 하나를 먹는다. 그러나 어떤 분은 특별한 분일 수 있다. 특별한 분에는 수석 종업원이 손님들에게 주목해 달라고 한 뒤, 접시가 비어 있지 않은 손님 한 명을 선택하고, 그 손님의 접시에서 몇 개의 팬케이크를 조심스럽게 들어 올려 다른 손님 한 명의 접시로 옮긴다. 그 다른 손님의 접시는 비어 있을 수도 있고 비어 있지 않을 수도 있다. 특별한 분에는 음식을 먹는 것이 무례하므로 어떤 손님도 먹지 않는다.

오늘 아침 당번 수석 종업원은 당신이며, 특별한 분이 있다면 어느 분을 특별하게 할지와 어떤 팬케이크를 어디로 옮길지를 결정하는 것이 당신의 일이다. 즉, 매분 아무것도 하지 않고 손님들이 먹게 두거나, 그 분을 특별한 분으로 선언하고 손님들의 식사를 중단시켜 위에서 설명한 대로 하나 이상의 팬케이크를 한 번 옮길 수 있다.

먹을 팬케이크가 더 이상 남아 있지 않으면 아침 식사가 끝난다. 얼마나 빨리 그렇게 만들 수 있는가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100.

작은 데이터 세트

시간 제한: 240초. 1 ≤ D ≤ 6. 1 ≤ $P_{i}$ ≤ 9.

큰 데이터 세트

시간 제한: 480초. 1 ≤ D ≤ 1000. 1 ≤ $P_{i}$ ≤ 1000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 비어 있지 않은 접시를 가진 손님의 수 D가 적힌 한 줄과, 이어서 그 손님들의 접시에 있는 팬케이크 수를 나타내는 공백으로 구분된 D개의 정수가 적힌 한 줄로 구성된다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y는 아침 식사를 끝내는 데 필요한 최소 시간(분)이다.

케이스 #1에서는 손님 한 명이 팬케이크 3개를 가지고 시작하고, 나머지 모든 손님의 접시는 비어 있다. 최적의 전략 중 하나는 다음과 같다.

1분: 아무것도 하지 않는다. 그 손님이 팬케이크 하나를 먹는다.

2분(특별): 식사를 중단시키고 그 손님의 팬케이크 더미에서 팬케이크 하나를 다른 손님의 빈 접시로 옮긴다. (처음에 팬케이크를 가진 손님이 몇 명이든, 빈 접시를 가진 손님은 항상 무한히 많이 있다는 점을 기억하라.) 식사를 중단한 동안에는 어떤 팬케이크도 먹지 않는다.

3분: 아무것도 하지 않는다. 그 두 손님이 마지막으로 남은 팬케이크 두 개 중 하나씩을 먹는다.

케이스 #2에서는 식사를 중단시키지 않고 손님들이 2분 동안 먹게 두는 것이 최적이며, 그동안 손님들은 모든 팬케이크를 다 먹는다.

케이스 #3에서는 손님 한 명이 팬케이크 4개를 가지고 시작하고, 나머지 모든 손님의 접시는 비어 있다. 첫 번째 분을 특별한 분으로 삼아 그 손님의 접시에서 팬케이크 두 개를 다른 손님의 빈 접시로 옮긴 다음, 두 번째와 세 번째 분에는 아무것도 하지 않고 손님들이 먹게 두는 것이 최적이다.