Osmos (Large)

아르민은 모트를 조종하는 게임을 한다. 모트는 다른 모트를 흡수하거나 다른 모트에게 흡수되는 작은 입자다.

아르민의 모트는 자기보다 크기가 엄격하게 작은 모트만 흡수한다. 크기가 같은 모트는 흡수하지 못한다. 모트를 흡수하면 그 모트의 크기가 아르민의 모트 크기에 더해지고, 커진 모트는 처음에는 건드릴 수 없던 모트까지 흡수할 수 있다.

예를 들어 아르민의 모트 크기가 $10$이고 나머지 모트의 크기가 $9$, $13$, $19$라고 하자. 처음에는 크기 $9$인 모트만 흡수할 수 있고, 흡수하면 크기가 $19$가 된다. 그다음 크기 $13$인 모트를 흡수해 $32$가 되고, 그제야 마지막 모트를 흡수할 수 있다.

아르민이 상대할 모트를 준비하는 쪽은 당신이다. 아르민의 모트 크기와 나머지 모트의 크기는 이미 정해져 있는데, 그 구성으로는 전부 흡수하는 방법이 아예 없을 수도 있다. 당신은 두 가지 연산을 순서와 횟수에 제한 없이 사용해 구성을 고칠 수 있다. 크기가 양의 정수인 모트를 새로 추가하거나, 이미 있는 모트 하나를 제거한다.

아르민의 모트가 나머지 모트를 전부 흡수할 수 있게 만드는 데 필요한 연산 횟수의 최솟값을 구하라.

예를 들어 아르민의 모트 크기가 $10$이고 나머지 모트가 $9$, $20$, $25$, $100$이면 지금 상태로는 전부 흡수하지 못한다. 크기 $3$인 모트를 추가하고 크기 $100$인 모트를 제거하면 연산 두 번으로 해결되므로 답은 $2$다.

첫째 줄에 게임의 수 $T$가 주어진다. 각 게임은 두 줄로 이루어진다. 첫째 줄에 아르민의 모트 크기 $A$와 나머지 모트의 개수 $N$이 주어진다. 둘째 줄에 나머지 모트 $N$개의 크기가 공백으로 구분되어 주어진다. 모든 크기는 정수다.

• $1 \le T \le 100$
• $1 \le A \le 10^6$
• $1 \le N \le 100$
• 나머지 모트의 크기는 모두 $1$ 이상 $10^6$ 이하다

각 게임마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 $1$부터 시작하는 게임 번호이고, $y$는 그 게임을 해결하는 데 필요한 연산 횟수의 최솟값이다.

입력으로 주어지는 크기는 $10^6$ 이하지만, 아르민의 모트는 흡수하는 동안 그 한계를 넘어 커질 수 있다. 새로 추가하는 모트의 크기에도 상한이 없고 양의 정수이기만 하면 된다.