题目描述

Up until today, the nation you live in has used $\mathbf{D}$ different positive integer denominations of coin for all transactions. Today, the queen got angry when a subject tried to pay his taxes with a giant sack of low-valued coins, and she just decreed that no more than $\mathbf{C}$ coins of any one denomination may be used in any one purchase. For instance, if $\mathbf{C} = 2$ and the existing denominations are $1$ and $5$, it is possible to buy something of value $11$ by using two $5$s and one $1$, or something of value $12$ by using two $5$s and two $1$s, but it is impossible to buy something of value $9$ or $17$.

You cannot directly challenge the queen's decree, but you happen to be in charge of the mint, and you can issue new denominations of coin. You want to make it possible for any item of positive value at most $\mathbf{V}$ to be purchased under the queen's new rules. (Note that this may not necessarily have been possible before the queen's decree.) Moreover, you want to introduce as few new denominations as possible, and your final combined set of pre-existing and new denominations may not have any repeats.

What is the smallest number of new denominations required?

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each consists of one line with three space-separated values $\mathbf{C}$, $\mathbf{D}$, and $\mathbf{V}$, followed by another line with $\mathbf{D}$ distinct space-separated values representing the preexisting denominations, in ascending order.

输出格式

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 minimum number of new denominations required, as described above.

4
1 2 3
1 2
1 3 6
1 2 5
2 1 3
3
1 6 100
1 5 10 25 50 100

Case #1: 0
Case #2: 1
Case #3: 1
Case #4: 3

提示

Sample Explanation

Note that Cases #3 and #4 are not within the limits for the Small dataset.

In Case #1, it is already possible to make all the required values ($1, 2$, and $3$) using at most one copy of each of the existing denominations.

In Case #2, it suffices to add a denomination of either $3$ or $4$ -- whichever you choose, only one new denomination is required.

In Case #3, the optimal solution is to add a denomination of $1$.

Limits

• $1 \leq \mathbf{T} \leq 100$.
• Each existing denomination $\leq \mathbf{V}$.

Small dataset(11 Pts)

• Time limit: 240 5 seconds.
• $\mathbf{C} = 1$.
• $1 \leq \mathbf{D} \leq 5$.
• $1 \leq \mathbf{V} \leq 30$.

Large dataset(23 Pts)

• Time limit: 480 10 seconds.
• $1 \leq \mathbf{C} \leq 100$.
• $1 \leq \mathbf{D} \leq 100$.
• $1 \leq \mathbf{V} \leq 10^9$.