题目描述

While the most typical type of dice have 6 sides, each of which shows a different integer 1 through 6, there are many games that use other types. In particular, a $d_k$ is a die with $k$ sides, each of which shows a different integer 1 through $k$. A $d6$ is a typical die, a $d4$ has four sides, and a $d1000000$ has one million sides.

In this problem, we start with a collection of $\mathbf{N}$ dice. The $i$-th die is a $d\mathbf{S}_i$, that is, it has $\mathbf{S}_i$ sides showing integers 1 through $\mathbf{S}_i$. A straight of length $\ell$ starting at $x$ is the list of integers $x$, $x + 1$, $\cdots$, $x + (\ell - 1)$. We want to choose some of the dice (possibly all) and pick one number from each to form a straight. What is the longest straight we can form in this way?

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case is described in two lines. The firstline of a test case contains a single integer $\mathbf{N}$, the number of dice in the game. The second line contains $\mathbf{N}$ integers $\mathbf{S}_1$, $\mathbf{S}_2$, $\cdots$, $\mathbf{S}_\mathbf{N}$, each representing the number of sides of a different die.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the maximum number of input dice that can be put in a straight.

4
4
6 10 12 8
6
5 4 5 4 4 4
10
10 10 7 6 7 4 4 5 7 4
1
10

Case #1: 4
Case #2: 5
Case #3: 9
Case #4: 1

提示

Sample Explanation

In Sample Case #1, there are multiple ways to form a straight using all $4$ dice. One possible way is shown in the image above.

In Sample Case #2, since none of the dice can show an integer greater than $5$, there is no way to have a straight with more than $5$ dice. There are multiple ways to form a straight with exactly $5$ dice. For example, pick the integers $4$ and $5$ for both $d5$'s and then integers $1, 2$, and $3$ for three of the $d4$'s to form $1, 2, 3, 4, 5$.

In Sample Case #3, it is possible to form the straight $1, 2, 3, 4, 5, 6, 7, 8, 9$ by discarding one $d4$ and using the $d4$'s, $d5$, and $d6$ to get $1$ through $4$; the $d7$'s to get $5$ through $7$; and the $d10$'s to get $8$ and $9$. There is no way to form a straight of length $10$, so this is the best that can be done.

In Sample Case #4, we can only form a straight of length $1$, but we can do so by picking any integer for the $d10$ we are given.

Limits

• $1 \leq \mathbf{T} \leq 100$.

Test Set 1 (9 Pts, Visible Verdict)

• $1 \leq \mathbf{N} \leq 10$.
• $4 \leq \mathbf{S}_i \leq 20$, for all $i$.

Test Set 2 (11 Pts, Visible Verdict)

• $1 \leq \mathbf{N} \leq 10^5$.
• $4 \leq \mathbf{S}_i \leq 10^6$, for all $i$.