외발자전거 세기

서커스 학교 생활은 안내 책자에서 본 것만큼 즐겁지 않다. 들어야 할 수업은 너무 많고, 공중그네 수업은 올라갔다 내려갔다를 반복하며, 외줄타기 수업에서는 줄이 팽팽하게 당겨져 있다.

그나마 즐거운 일은 같은 반 친구들과 외발자전거를 타는 것이다. 바퀴 크기는 저마다 다르고, 타이어는 한 바퀴 구를 때마다 땅에 작은 자국을 하나 남긴다. 어느 날 도로에 남은 자국을 보고, 숙제 대신 이 자국을 남겼을 외발자전거가 최소 몇 대인지 세어 보기로 한다.

도로 한 구간은 위치 $0, 1, \dots, m-1$로 나타낸다. 외발자전거는 도로의 처음부터 끝까지 전부 달린다. 바퀴 둘레는 정수 $c \ge 1$이고, 첫 자국을 남기는 위치 $s$는 $0 \le s < c$를 만족한다. 따라서 이 외발자전거는 $s, s+c, s+2c, \dots$ 가운데 $m$보다 작은 모든 위치에 자국을 남긴다.

도로 위에 남은 자국은 빠짐없이 관찰했으므로, 어떤 외발자전거도 관찰하지 못한 위치에는 자국을 남기지 않는다. 서로 다른 외발자전거가 같은 위치에 자국을 남기는 것은 가능하다.

도로의 길이와 관찰한 자국의 위치가 주어지면, 그 자국을 남겼을 수 있는 외발자전거의 최소 대수를 구하라.

입력의 각 줄은 도로 한 구간의 관찰 결과다. 각 줄은 두 정수 $m$과 $n$ ($1 \le m \le 100$, $1 \le n \le 10$)으로 시작한다. $m$은 도로의 길이, $n$은 관찰한 자국의 개수다. 이어서 서로 다른 정수 $a_1, a_2, \dots, a_n$ ($0 \le a_i < m$)이 주어지며, 자국이 남은 위치를 뜻한다. 입력은 최대 100줄이고, 파일의 끝에서 끝난다.

각 구간마다 관찰한 자국을 남겼을 수 있는 외발자전거의 최소 대수를 한 줄에 하나씩 출력한다.