Less Money, More Problems (Large)

Until today, the country you live in has used $D$ different positive integer coin denominations for every transaction. Today a subject tried to pay his taxes with a giant sack of low value coins, the queen lost her temper, and she decreed that no single purchase may use more than $C$ coins of any one denomination. For example, if $C = 2$ and the existing denominations are 1 and 5, you can buy an item worth 11 with two 5s and one 1, and you can buy an item worth 12 with two 5s and two 1s, but you cannot buy an item worth 9 or an item worth 17.

You cannot defy the decree directly. You do run the mint, so you can issue coins of new denominations. You want every item whose value is a positive integer at most $V$ to be purchasable under the new rule. (This may not have been possible even before the decree.) You want to introduce as few new denominations as possible, and the final set of old and new denominations may not contain the same value twice.

Print the smallest number of new denominations you need.

The first line contains the number of test cases $T$. Then $T$ test cases follow. Each test case consists of one line with three space separated integers $C$, $D$, and $V$, followed by one line with the $D$ existing denominations in ascending order, separated by spaces. The existing denominations are pairwise distinct.

Limits

• $1 \le T \le 100$
• $1 \le C \le 100$
• $1 \le D \le 100$
• $1 \le V \le 10^9$
• every existing denomination is a positive integer at most $V$

For each test case, print one line in the form Case #x: y, where x is the test case number starting from 1 and y is the minimum number of new denominations.

In the first test case of the example, the existing denominations 1 and 2 already cover the required values 1, 2, and 3 with one copy of each.

In the second test case, adding either denomination 3 or denomination 4 is enough, so one new denomination suffices whichever you pick.

In the third test case, adding denomination 1 is optimal.