공평한 간식 제공

Aroha는 동물을 매우 사랑해서 여가 시간 중 일부를 자신이 사랑하는 여러 사람의 반려동물을 돌보며 보낸다. Aroha는 반려동물들에게 간식을 주는 것을 좋아하지만, 공평한 방식으로 주고 싶어 한다.

Aroha는 크기가 같은 반려동물들이 같은 양의 간식을 받고, 더 큰 반려동물들이 더 작은 반려동물들보다 반드시 더 많은 간식을 받는 것이 합리적이라고 판단했다. 예를 들어, 크기가 $10, 20, 10$와 $25$인 반려동물 $4$마리가 함께 있다면, 크기가 $10$인 각 반려동물에게 간식 $2$개, 크기가 $20$인 반려동물에게 간식 $3$개, 크기가 $25$인 반려동물에게 간식 $5$개를 줄 수 있다. 그러려면 간식을 총 $2+3+2+5=12$개 사야 한다. 하지만 크기가 $10$인 반려동물들에게 각각 $1$개, 크기가 $20$인 반려동물에게 $2$개, 크기가 $25$인 반려동물에게 $3$개를 주면, 총 $7$개의 간식만으로도 반려동물 $4$마리 모두에게 간식을 주면서 자신의 규칙을 지킬 수 있다.

Aroha가 다음 반려동물 돌봄 날을 계획하도록 도와주자. 함께할 모든 반려동물의 크기가 주어질 때, Aroha가 자신의 공평성 규칙을 지키면서 모든 반려동물에게 적어도 하나의 간식을 줄 수 있도록 사야 하는 간식 수의 최솟값을 계산하라.

제한

시간 제한: 10초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $1 \le \mathbf{S_i} \le 100$.

테스트 세트 1 (결과 공개)

$2 \le \mathbf{N} \le 5$.

테스트 세트 2 (결과 공개)

$2 \le \mathbf{N} \le 100$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 구성된다. 테스트 케이스의 첫 줄에는 Aroha의 다음 반려동물 돌봄 날에 함께할 반려동물의 수를 나타내는 정수 $\mathbf{N}$ 하나가 주어진다. 테스트 케이스의 두 번째 줄에는 각 반려동물의 크기를 나타내는 $\mathbf{N}$개의 정수 $\mathbf{S_1}, \mathbf{S_2}, \dots, \mathbf{S_N}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 Aroha가 자신의 공평성 규칙을 지키면서 모든 반려동물에게 적어도 하나의 간식을 줄 수 있도록 사야 하는 간식 수의 최솟값이다.

예제 케이스 #1은 위에서 설명한 케이스이다.

예제 케이스 #2에서는 모든 반려동물의 크기가 같으므로 Aroha는 모두에게 같은 양의 간식을 주어야 한다. 각 반려동물에게 간식 하나를 주면 총개수가 최소가 된다.

예제 케이스 #3에서는 두 반려동물의 크기가 서로 다르므로 각각 서로 다른 양의 간식을 받아야 한다. 간식을 $2$개보다 적게 사면 두 반려동물 모두에게 간식을 주기에 충분하지 않다. 간식을 $2$개 사고 두 반려동물이 모두 무언가를 받도록 하면, 두 반려동물의 크기가 다른데도 Aroha는 둘에게 같은 양을 줄 수밖에 없다. Aroha는 간식 $3$개를 사용하여 작은 반려동물에게 $1$개, 큰 반려동물에게 $2$개를 줌으로써 자신의 모든 규칙을 지킬 수 있다.