Bạn được cho \(k\) số nguyên tố phân biệt \(a_1, a_2, \ldots, a_k\) và một số nguyên \(n\).

Nhiệm vụ của bạn là tính toán có bao nhiêu trong \(n\) số nguyên dương đầu tiên chia hết cho ít nhất một trong các số nguyên tố đã cho.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(k\)
• Dòng thứ hai có \(k\) số nguyên tố \(a_1, a_2, \ldots, a_k\)

Constraints

• \(1 \leq n \leq 10^{18}\)
• \(1 \leq k \leq 20\)
• \(2 \leq a_i \leq n\)

Output

• In một số nguyên: số lượng số nguyên trong khoảng \(1, 2, \ldots, n\) chia hết cho ít nhất một trong các số nguyên tố.

Example

20 2
2 5

12