Simple task

Determine the count of natural numbers within the interval from a to b, inclusive, that are not divisible by any of the specified distinct prime numbers p[i].

Input

The first line provides two integers, a and b (1 ≤ a ≤ b ≤ 10^18), representing the interval's boundaries. The second line specifies the number of prime numbers, n (1 ≤ n ≤ 9). The third line lists the prime numbers p[i], each of which is distinct and does not exceed 100.

Output

Print the count of natural numbers that meet the criteria.

Examples