Simple task — Eolymp

Input

The first line provides two integers, $a$ and $b$ ( $1 \leq a \leq b \leq 1 0^{18}$ 1 \le a \le b \le 10^{18}), representing the interval's boundaries. The second line specifies the number of prime numbers, $n$ ( $1 \leq n \leq 9$ 1 \le n \le 9). The third line lists the prime numbers $p_{i}$ p_i, each of which is distinct and does not exceed $100$ .

Output

Print the count of natural numbers that meet the criteria.

Examples

Example 1

Loading

Example 2

Loading

Example 3

Loading

Example 4

Loading