Less Money, More Problems

Until today, the country you live in settled every purchase with $D$ distinct positive integer coin denominations. This morning a subject tried to pay his taxes with a huge sack of low value coins, the queen lost her temper, and she decreed that a single purchase may use at most $C$ coins of any one denomination.

Take $C = 2$ with existing denominations 1 and 5. You can buy an item worth 11 with two 5s and one 1, and an item worth 12 with two 5s and two 1s, but an item worth 9 or 17 cannot be bought at all.

You cannot challenge the decree directly. You do run the mint, so you can issue coins of new denominations. You want every item whose price is a positive integer at most $V$ to be payable under the new rule. This was not necessarily possible before the decree either. You want to issue as few new denominations as you can, and the final set of old and new denominations must contain no repeated value.

Find the smallest number of new denominations you have to issue.

The first line contains the number of test cases $T$. Each test case takes two lines. The first line contains three space separated integers $C$, $D$, and $V$. The second line contains the $D$ existing denominations, distinct and in ascending order.

Limits

• $1 \le T \le 100$
• $1 \le C \le 10^{15}$
• $1 \le D \le 100$
• $1 \le V \le 10^{15}$
• Every existing denomination is a positive integer at most $V$, and the $D$ values are distinct.

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 smallest number of new denominations.