무한 팬케이크 하우스 (Large)

무한 팬케이크 하우스에는 팬케이크가 유한하게 있지만, 그 팬케이크를 먹으려는 손님은 무한히 많다. 가게가 아침 영업을 시작할 때 무한히 많은 손님 가운데 정확히 $D$명의 접시에만 팬케이크가 놓여 있고, 그중 $i$번째 손님의 접시에는 팬케이크가 $P_i$개 있다. 나머지 손님의 접시는 모두 비어 있다.

보통은 1분마다 접시가 비어 있지 않은 손님이 각자 자기 접시에서 팬케이크를 하나씩 먹는다. 그런데 어떤 1분은 특별한 분이 되기도 한다. 특별한 분에는 수석 서버가 손님들의 주의를 끈 다음, 접시가 비어 있지 않은 손님 한 명을 골라 그 접시에서 팬케이크를 몇 개 들어 올려 다른 손님 한 명의 접시로 옮긴다. 옮기는 쪽 접시는 비어 있어도 되고 비어 있지 않아도 된다. 특별한 분에는 아무도 팬케이크를 먹지 않는다. 먹는 것이 예의가 아니기 때문이다.

당신은 오늘 아침 근무하는 수석 서버다. 어느 분을 특별한 분으로 삼을지, 그리고 어떤 팬케이크를 어디로 옮길지 정하는 것이 당신의 일이다. 즉 1분마다 아무것도 하지 않고 손님들이 먹게 두거나, 특별한 분을 선언해 손님들을 멈추고 위에서 설명한 대로 팬케이크를 한 번 옮길 수 있다.

먹을 팬케이크가 하나도 남지 않으면 아침 식사가 끝난다. 아침 식사를 최소 몇 분 만에 끝낼 수 있는가?

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄이다. 첫 줄에는 접시가 비어 있지 않은 손님의 수 $D$가 주어지고, 둘째 줄에는 그 손님들의 접시에 놓인 팬케이크 개수를 나타내는 정수 $D$개가 공백으로 구분되어 주어진다.

제한

• $1 \le T \le 100$
• $1 \le D \le 1000$
• $1 \le P_i \le 1000$

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 아침 식사를 끝내는 데 필요한 최소 시간을 분 단위로 나타낸 값이다.

첫 번째 테스트 케이스에서는 한 손님이 팬케이크 3개로 시작하고 나머지 손님의 접시는 비어 있다. 최적 전략 하나는 다음과 같다.

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

2분(특별한 분): 손님들을 멈추고 그 손님의 접시에서 팬케이크 하나를 비어 있는 다른 접시로 옮긴다. 처음에 팬케이크를 가진 손님이 몇 명이든 접시가 비어 있는 손님은 언제나 무한히 많다. 특별한 분에는 아무도 팬케이크를 먹지 않는다.

3분: 아무것도 하지 않는다. 두 손님이 남은 팬케이크 2개를 하나씩 먹는다.

두 번째 테스트 케이스에서는 한 번도 멈추지 않고 2분 동안 그대로 먹게 두는 것이 최적이고, 그 사이에 팬케이크가 모두 없어진다.

세 번째 테스트 케이스에서는 한 손님이 팬케이크 4개로 시작하고 나머지 접시는 비어 있다. 첫 1분을 특별한 분으로 써서 팬케이크 2개를 비어 있는 다른 접시로 옮기고, 2분과 3분에는 아무것도 하지 않고 먹게 두는 것이 최적이다.