In a Circular City, there are $n$ houses, numbered from 1 to n and arranged in 1,2,...,n,1,2,...
Chef needs to deliver packages to $m$ (m≤n) houses.

Chef is initially at house 1. Chef decides an integer $x$ and stops after every $x$ houses. i.e- if $n=7$ and $x=2$. He will stop at 1,3,5,7,2,... He may deliver a package when he stops at a house. His work is done when all the packages are delivered.

What is the minimum number of times Chef has to stop, if he can choose any $x$ ?

Note: Starting point (1) is also counted in number of stops

------ Input: ------

First line will contain $n, m$, denoting number of houses and number of packages respectively.
Next line contains $m$ distinct space separated integers denoting the houses

------ Output: ------
Single line containing an integer denoting minimum number of stops.

------ Constraints ------
$3 ≤ n ≤ 1000$
$1 ≤ m ≤ n$

----- Sample Input 1 ------
5 3
1 2 4
----- Sample Output 1 ------
3
----- explanation 1 ------
For first input,
If Chef chooses $x=3$, he will stop at 1, 4, 2 before delivering all the packages.

----- Sample Input 2 ------
6 2
3 4
----- Sample Output 2 ------
4
----- explanation 2 ------
For second,
If Chef chooses $x=1$, he will stop at 1, 2, 3, 4 before delivering all the packages.

见题面

见题面