울타리

우리는 매우 긴 울타리를 세우려고 한다. 이미 울타리를 세울 좋은 장소를 찾았으며, 이제 남은 일은 재료를 모으는 것뿐이다.

지역 철물점에서 다양한 길이로 제공되는 나무판자를 각각 무제한으로 살 수 있다. 낭비를 피하기 위해 이 판자들의 전체 길이가 세우려는 울타리의 길이와 정확히 같도록 하고자 한다.

울타리의 길이와 사용할 수 있는 판자의 길이들이 주어질 때, 정확히 필요한 길이를 만들기 위해 구매해야 하는 판자의 최소 개수는 얼마인가?

주의하라. 울타리는 매우 길 것이다!

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 50. $10^{10}$ ≤ L ≤ $10^{18}$. 1 ≤ N ≤ 100.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ $B_{i}$ ≤ 100.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ $B_{i}$ ≤ 100000.

입력 파일의 첫 줄에는 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 두 줄로 구성된다. 첫 줄에는 공백으로 구분된 정수 L과 N이 주어진다. 이들은 각각 울타리의 전체 길이와 구매할 수 있는 서로 다른 판자 길이의 개수를 나타낸다. 두 번째 줄에는 가능한 모든 판자 길이를 나타내는 공백으로 구분된 N개의 정수 $B_{1}$, $B_{2}$, ..., $B_{N}$이 주어진다.

각 테스트 케이스마다 "Case #x: M"을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, M은 다음과 같다.

• 하나 이상의 판자를 구매하여 전체 길이가 L과 정확히 같아지게 할 수 있다면, M은 이를 위해 필요한 판자의 최소 개수여야 한다.

• 그렇지 않으면 M은 문자열 "IMPOSSIBLE"이어야 한다.

설명

첫 번째 예제에서 최적의 전략은 길이가 23인 판자 2개, 길이가 51인 판자 5개, 길이가 100인 판자 99999997개를 사용하는 것이다. 물론 길이가 100인 판자 100000001개만 사용하여 전체 길이를 L보다 크게 만들 수도 있지만, 이는 허용되지 않는다.

두 번째 예제에서는 짝수 길이만 만들 수 있다.