Page not loading? Try clicking here.
Placeholder

#10423

d1000000 5s 1024MB

Problems

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 dk 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.

Dice from sample case 1

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, \dots, 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?


Input

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 first line 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}, \dots, \mathbf{S_N}, each representing the number of sides of a different die.


Output

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.


Example 

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
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.

Source

GCJ 2022qr C

You must sign in to write code.