Fence

You are building a very long fence. The site is already chosen, so all that is left is collecting the material.

The hardware stores nearby sell wooden boards in several lengths, and you can buy as many boards of each length as you want. To waste nothing, the total length of the boards you buy has to 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 so that their total length is exactly right.

Be careful: the fence is going to be very long.

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

Each test case consists of two lines. The first line contains the total length of the fence $L$ and the number of different board lengths on sale $N$, separated by a space. The second line contains the board lengths $B_1, B_2, \dots, 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 100$

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

• If you can buy one or more boards whose total length is exactly $L$, then $M$ is the minimum number of boards needed to do that.
• Otherwise $M$ is the string "IMPOSSIBLE".

In the first case of the example, the best purchase 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$, and that is not allowed.

In the second case of the example, only even lengths can be reached.