Find My Friend

Max feels lonely after shifting to a new locality, as he does not have any friend there. So his parents bought him a new number from the Integers SuperMarket! Every child in the locality has bought a number from the same market.

He takes the number to go play with other children in the locality. But to his surprise, there is a rule in the locality, two people A and B can only be considered friends if numbers with A and B are not Coprime, i.e they have a common factor other than 1.

You are given the number that Max bought and the numbers of other children in the locality. Can you find how many friends he can have?

Input:
First line contains an integer A, the number that Max has.
Second line contains N, the count of children in the locality.
Third line contains N space-separated integers, where X_i is the integer with the i^th child.

Output:
Output the maximum number of friends that Max can make.

Constraints:
1 ≤ A ≤ 10³
1 ≤ N ≤ 10³
1 ≤ X_i ≤ 10³

Sample Input

6
3
4 7 12

Sample Output



2
Explanation

Puchi can become friends with First and Third child.