익스트림 에스컬레이터 포고 (라지)

로빗 다우니 호퍼는 위험한 스포츠인 익스트림 에스컬레이터 포고를 만든 사람이다. 집에 에스컬레이터가 있어도 절대 따라 하지 마라.

익스트림 에스컬레이터 포고에는 두 가지가 필요하다. 뛰어오르는 도구인 포고 스틱, 그리고 계단 $N$개가 일정한 속도로 올라가는 빠른 에스컬레이터다. 계단 중 일부는 빨간색이고 나머지는 파란색이다. 로빗은 포고 스틱을 탄 채로 에스컬레이터 중간의 파란 계단 하나에 착지하면서 경기를 시작한다. 그다음부터는 계단이 발밑으로 지나가는 동안 계속 수직으로 뛰어오른다. 착지는 파란 계단에만 해야 한다. 빨간 계단에 착지하면 탈락하고, 도전자 리피 프로기슨이 다음 차례로 뛴다. 더 높이 뛴 쪽이 이긴다.

첫 파란 계단을 밟은 뒤, 로빗은 항상 높이 1로 뛰어올라 바로 다음 계단에 착지한다. 그 계단이 파란색이어야 하고, 빨간색이면 로빗은 탈락한다. 그 뒤의 각 점프에서는 세 가지 중 하나를 고른다.

• 점프를 낮춰 높이를 1 줄인다.
• 지금 점프와 같은 높이로 뛴다.
• 점프를 키워 높이를 1 늘린다.

높이가 $H$인 점프는 계단 $H$개가 로빗의 발밑을 지나가는 시간만큼 이어진다. 즉 계단 $p$에서 높이 $H$로 뛰면 $p$에서 $H$칸 뒤의 계단에 착지한다. 높이가 0인 점프는 할 수 없고, 높이의 상한은 없다. 계단은 끝없이 순환하므로 계단 $N$ 다음 계단은 다시 계단 1이다.

빨간 계단에 착지하는 점프도 로빗이 이미 뛴 점프이므로, 그 높이는 도달한 높이로 기록한다.

$N$과 각 계단의 색이 주어진다. 시작 계단과 점프 순서를 골라서 로빗이 도달하는 가장 높은 높이를 최대로 만들어라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 다음 $T$개의 줄에는 각각 정수 $N$, 정수 $K$, 그리고 파란 계단의 번호인 1 이상 $N$ 이하의 정수 $K$개가 주어진다. 목록에 없는 계단은 모두 빨간색이다. 계단 $N$ 다음 계단은 계단 1이다.

제한

• $1 \le T \le 100$
• $3 \le N \le 10^9$
• $1 \le K \le \min(N, 1000)$
• 파란 계단의 번호는 서로 다르고, 증가하는 순서로 주어진다.

각 테스트 케이스마다 "Case #$x$: $H$" 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $H$는 로빗이 도달할 수 있는 가장 높은 높이다. 높이에 제한이 없으면 $H$ 자리에 "infinity"를 출력한다.

첫 번째 예제의 첫째 케이스에서 로빗이 할 수 있는 최선은 계단 2에서 시작해 높이 1로 뛰어 계단 3에 착지하고, 다시 높이 2로 뛰어 빨간 계단 1에 착지하는 것이다. 이렇게 도달한 가장 높은 높이는 2다.

둘째 케이스의 최선은 계단 5에서 시작해 높이 1로 계단 6, 높이 2로 계단 8, 높이 3으로 계단 1, 높이 4로 계단 5, 높이 5로 계단 10에 착지하는 것이다. 계단 10은 빨간색이므로 여기서 끝나고 답은 5다.

셋째 케이스에서는 계단 1에서 시작해 영원히 뛸 수 있으므로 원하는 높이에 모두 도달한다.