Divisibility — Eolymp

Input

The input consists of multiple test cases. The first line of each test case contains two integers $l (1 \leq l \leq 1 0^{9})$ l~(1 \le l \le 10^9) and $r (1 \leq r \leq 1 0^{9})$ r~(1 \le r \le 10^9), which define the range boundaries. The second line contains the number of elements $n (1 \leq n \leq 18)$ n~(1 \le n \le 18) in the set and the set of integers $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n. Each integer in the set is between $1$ and $1 0^{9}$ 10^9.

Output

For each test case, output a single line containing the number of integers in the range $[l, r]$ [l, r] that are divisible by at least one number from the set $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n.

Examples

Example 1

Loading