d1000000

가장 일반적인 주사위는 $6$개의 면을 가지며 각 면에는 $1$부터 $6$까지의 서로 다른 정수가 표시되어 있지만, 다른 종류의 주사위를 사용하는 게임도 많다. 특히 $dk$는 $k$개의 면을 가지며 각 면에 $1$부터 $k$까지의 서로 다른 정수가 표시된 주사위이다. $d6$는 일반적인 주사위이고, $d4$는 면이 네 개이며, $d1000000$는 면이 백만 개이다.

이 문제에서는 $\mathbf{N}$개의 주사위 모음으로 시작한다. $i$번째 주사위는 $d\mathbf{S_i}$이다. 즉, 이 주사위에는 $\mathbf{S_i}$개의 면이 있고, 각 면에는 $1$부터 $\mathbf{S_i}$까지의 정수가 표시되어 있다. $x$에서 시작하는 길이 $\ell$의 연속 수열은 정수 목록 $x, x + 1, \dots, x + (\ell - 1)$이다. 주사위 중 일부를 선택하고(전부를 선택해도 된다), 각 주사위에서 수 하나씩을 골라 연속 수열을 만들고자 한다. 이 방법으로 만들 수 있는 가장 긴 연속 수열의 길이는 얼마인가?

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$.

테스트 세트 1 (Visible Verdict)

시간 제한: 5초. $1 \le \mathbf{N} \le 10$. 모든 $i$에 대해 $4 \le \mathbf{S_i} \le 20$.

테스트 세트 2 (Visible Verdict)

시간 제한: 15초. $1 \le \mathbf{N} \le 10^5$. 모든 $i$에 대해 $4 \le \mathbf{S_i} \le 10^6$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 설명된다. 테스트 케이스의 첫 번째 줄에는 게임에 사용되는 주사위의 수를 나타내는 정수 하나 $\mathbf{N}$이 주어진다. 두 번째 줄에는 $\mathbf{N}$개의 정수 $\mathbf{S_1}, \mathbf{S_2}, \dots, \mathbf{S_N}$가 주어지며, 각각은 서로 다른 주사위 하나의 면 개수를 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며(1부터 시작한다), $y$는 연속 수열에 포함할 수 있는 입력 주사위 수의 최댓값이다.

예제 케이스 #1에서는 $4$개의 주사위를 모두 사용해 연속 수열을 만드는 방법이 여러 가지 있다. 가능한 방법 하나가 위 이미지에 나와 있다.

예제 케이스 #2에서는 어떤 주사위도 $5$보다 큰 정수를 표시할 수 없으므로, $5$개보다 많은 주사위로 연속 수열을 만들 방법은 없다. 정확히 $5$개의 주사위로 연속 수열을 만드는 방법은 여러 가지 있다. 예를 들어, 두 $d5$⁠에서 각각 정수 $4$와 $5$를 고른 다음, $d4$⁠ 중 세 개에서 정수 $1, 2,$와 $3$를 골라 $1,2,3,4,5$을 만든다.

예제 케이스 #3에서는 $d4$ 하나를 버리고, $d4$⁠들, $d5$, $d6$를 사용해 $1$부터 $4$까지를 얻고, $d7$⁠들을 사용해 $5$부터 $7$까지를 얻으며, $d10$⁠들을 사용해 $8$와 $9$를 얻음으로써 연속 수열 $1,2,3,4,5,6,7,8,9$를 만들 수 있다. 길이 $10$의 연속 수열을 만들 방법은 없으므로, 이것이 가능한 최선이다.

예제 케이스 #4에서는 길이 $1$의 연속 수열만 만들 수 있지만, 주어진 $d10$에서 어떤 정수든 골라 그렇게 할 수 있다.