Osmos

Armin은 Hemisphere Games에서 개발한 물리 기반 퍼즐 게임 Osmos를 플레이하고 있다. 이 게임에서 그는 "mote"가 되어 돌아다니며 자신보다 작은 모트를 흡수한다.

영어에서 "mote"는 작은 입자를 뜻한다. 이 게임에서는 다른 것들을 흡수하거나 다른 것에 흡수되는 물체이다! 이 문제의 게임은 Osmos와 비슷한 발상을 사용하지만, Osmos를 플레이해 보았다고 가정하지 않는다.

Armin의 모트가 자신보다 작은 모트를 흡수하면, 그의 모트는 그 작은 모트의 크기만큼 커진다. 이제 더 커졌으므로 더 많은 모트를 흡수할 수 있게 될 수도 있다. 예를 들어 Armin의 모트 크기가 10이고, 다른 모트들의 크기가 9, 13, 19이라고 하자. 처음에 Armin의 모트는 크기가 9인 모트만 흡수할 수 있다. 이를 흡수하면 크기가 19이 된다. 그러면 크기가 13인 모트만 흡수할 수 있다. 이를 흡수하면 크기가 32이 된다. 이제 Armin의 모트는 마지막 모트를 흡수할 수 있다.

Armin의 모트가 다른 모트를 흡수할 수 있는 것은 그 다른 모트가 더 작을 때, 그리고 그럴 때에만 가능하다는 점에 유의한다. 다른 모트의 크기가 그의 모트와 같다면 그의 모트는 이를 흡수할 수 없다.

당신은 Armin이 흡수할 모트들을 생성하는 프로그램을 담당한다. 프로그램은 이미 크기가 다양한 모트 몇 개와 Armin의 모트를 생성했다. 안타깝게도 그의 모트 크기와 다른 모트들의 목록에 따라서는 Armin의 모트가 이들을 모두 흡수할 방법이 없을 수 있다.

이 문제를 해결하려고 한다. 다음 두 종류의 연산을 임의의 순서로 횟수 제한 없이 수행할 수 있다. 임의의 양의 정수 크기를 가진 모트를 게임에 추가하거나, 기존 모트 중 어느 하나를 제거할 수 있다. Armin의 모트가 다른 모든 모트를 흡수할 수 있게 만드는 데 필요한 연산의 최소 횟수는 얼마인가?

예를 들어 Armin의 모트 크기가 10이고 다른 모트들의 크기가 $[9, 20, 25, 100]$라고 하자. 현재 이 게임은 해결할 수 없지만, 크기가 3인 모트를 추가하고 크기가 100인 모트를 제거하면 단 2번의 연산으로 해결할 수 있게 만들 수 있다. 여기서 정답은 2이다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100.

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

1 ≤ A ≤ 100. 1 ≤ 모든 모트의 크기 ≤ 100. 1 ≤ N ≤ 10.

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

1 ≤ A ≤ $10^{6}$. 1 ≤ 모든 모트의 크기 ≤ $10^{6}$. 1 ≤ N ≤ 100.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 Armin의 모트 크기 A와 다른 모트의 수 N이 주어진다. 둘째 줄에는 다른 모트 N개의 크기가 주어진다. 주어지는 모든 모트의 크기는 정수이다.

각 테스트 케이스마다 "Case #x: y"을 담은 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작하고, y는 게임을 해결할 수 있게 만드는 데 필요한 연산의 최소 횟수이다.

입력 파일에서는 모트의 크기가 제한되어 있지만, Armin의 모트는 다른 모트들을 흡수하여 주어진 제한보다 더 커질 수 있다.

Osmos는 Hemisphere Games에서 만들었다. Hemisphere Games는 Google Code Jam을 보증하지 않으며 이에 관여하지도 않는다.