Unicycle counting

Going to circus college is not as fun as you were led to believe. You are juggling so many classes. Trapeze class is sometimes up, sometimes down. There’s a lot of tension in your high-wire class. And you’ve seen that lion taming can be cat-astrophic.

The one pleasure you find is in riding unicycles with your fellow classmates. Many people have unicycles with different sized wheels. One day you notice that all their tires leave a small mark on the ground, once per rotation. You decide to amuse yourself and avoid your classwork by trying to determine how many unicycles have passed by on a given stretch of road. In fact, you want to know the minimum number of unique unicycles that could have left the marks you observe. You make the simplifying assumption that any unicycle riding on the road will ride completely from the beginning to the end.

The figures below illustrate the sample input. Each thick black vertical stripe represents a mark left by a tire.

Input

Each line of input represents the observations on a stretch of road. A line begins with two integers $1 \leq m \leq 100$ and $1 \leq n \leq 10$, where $m$ represents the length of the road and $n$ represents the number of marks you observe on the road. These are followed by $n$ unique integers $a_1, a_2, \ldots , a_ n$, where $0 \leq a_ i < m$ for all $a_ i$. These $n$ integers represent the positions where you observed a unicycle’s tire has left a mark. There will be at most 100 lines of input. Input ends at end of file.

Output

For each set of observations, print the minimum number of unicycles that could have produced the observed marks.

10 5 1 3 5 7 9
10 4 1 3 7 9
20 10 0 4 5 7 8 10 12 14 15 16

1
2
3