Osmos (Large)

Armin plays a game about motes. A mote is a small particle that absorbs other motes, or is absorbed by them.

Armin controls one mote. His mote absorbs another mote only if the other mote is strictly smaller. A mote of exactly the same size cannot be absorbed. Absorbing a mote adds that mote's size to Armin's mote, so his mote grows and may then absorb motes it could not touch before.

For example, suppose Armin's mote has size $10$ and the other motes have sizes $9$, $13$ and $19$. At the start his mote can absorb only the mote of size $9$, which brings it to size $19$. Then it absorbs the mote of size $13$ and reaches size $32$, and only then can it absorb the last mote.

You prepare the motes Armin plays against. The size of Armin's mote and the sizes of the other motes are already fixed, and that set may leave no way for his mote to absorb everything. You may repair it with two operations, used in any order and any number of times: add a new mote of any positive integer size, or remove one of the existing motes.

Report the minimum number of operations that makes it possible for Armin's mote to absorb every other mote.

For example, if Armin's mote has size $10$ and the other motes are $9$, $20$, $25$ and $100$, the game is not solvable as it stands. Adding a mote of size $3$ and removing the mote of size $100$ solves it in two operations, so the answer is $2$.

The first line has the number of games $T$. Each game takes two lines. The first line has the size of Armin's mote $A$ and the number of other motes $N$. The second line has the $N$ sizes of the other motes, separated by spaces. Every size is an integer.

• $1 \le T \le 100$
• $1 \le A \le 10^6$
• $1 \le N \le 100$
• every other mote size is between $1$ and $10^6$

For each game print one line in the form Case #x: y, where $x$ is the game number starting at $1$ and $y$ is the minimum number of operations that solves that game.

The sizes given in the input are at most $10^6$, but Armin's mote can grow past that bound while it absorbs. A mote you add has no upper bound either, it only has to be a positive integer.