Fence Boards

You are planning a very long fence. The site is already chosen, and the only work left is collecting the material.

Local hardware stores sell wooden boards in several lengths, and you can buy as many of each length as you want. To avoid waste, the total length of the boards you buy must be exactly the length of the fence.

Given the length of the fence and the board lengths on sale, find the minimum number of boards you have to buy to reach that total exactly.

Note that the fence is very long.

The first line contains the number of test cases $T$. $T$ test cases follow.

Each test case consists of two lines. The first line contains two space-separated integers $L$ and $N$. $L$ is the total length of the fence and $N$ is the number of different board lengths on sale. The second line contains the board lengths $B_1, B_2, \ldots, B_N$, separated by spaces.

Limits

• $1 \le T \le 50$
• $10^{10} \le L \le 10^{18}$
• $1 \le N \le 100$
• $1 \le B_i \le 100000$

For each test case, print one line in the form Case #x: M, where $x$ is the case number starting from 1 and $M$ is as follows.

• If one or more boards can be bought so that their total length is exactly $L$, then $M$ is the minimum number of boards that does this.
• Otherwise $M$ is the string IMPOSSIBLE.

In the first case of the example, the best choice is 2 boards of length 23, 5 boards of length 51, and 99999997 boards of length 100. Buying 100000001 boards of length 100 gives a total greater than $L$, which is not allowed.

In the second case, only even lengths can be made.