무한 팬케이크 식당 (스몰)

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

평소에는 1분마다 접시가 비어 있지 않은 손님이 각자 자기 접시에서 팬케이크를 하나씩 먹는다. 그런데 어떤 1분은 특별한 1분이 될 수 있다. 특별한 1분에는 수석 서버가 손님들의 주의를 모은 다음, 접시가 비어 있지 않은 손님을 한 명 골라 그 접시에서 팬케이크를 몇 개 들어 다른 손님 한 명의 접시로 옮긴다. 옮겨 놓는 접시는 비어 있어도 되고 비어 있지 않아도 된다. 서버가 말하는 동안 먹는 것은 무례하므로 특별한 1분에는 아무도 먹지 않는다.

오늘 아침 수석 서버는 당신이다. 어느 1분을 특별한 1분으로 삼을지, 팬케이크를 어디로 옮길지 정하는 일이 당신의 몫이다. 다시 말해 매 분마다 아무것도 하지 않고 손님들이 먹게 두거나, 특별한 1분을 선언해 팬케이크 한 개 이상을 한 번 옮길 수 있다.

남은 팬케이크가 하나도 없으면 아침 식사가 끝난다. 아침 식사를 끝내는 데 걸리는 최소 시간을 구하라.

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

제한

• $1 \le T \le 100$
• $1 \le D \le 6$
• $1 \le P_i \le 9$

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

첫 번째 예제 테스트 케이스에서는 한 손님이 팬케이크 3개를 들고 시작하고 나머지 접시는 모두 비어 있다. 최적의 진행 방법 하나는 다음과 같다.

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

2분(특별한 1분): 그 손님의 접시에서 팬케이크 하나를 비어 있는 접시로 옮긴다. 처음에 팬케이크를 든 손님이 몇 명이든, 접시가 빈 손님은 항상 무한히 많다. 특별한 1분에는 아무도 먹지 않는다.

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

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

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