Given $n$ prime numbers $P_1, P_2,\ldots, P_n$, count the number of integers in the range $[L,R]$ that are divisible by exactly one prime in $P$.

Input

• The first line contains 3 integers $n, L, R$.
• The second line contains $n$ primes $P_i$. It is guaranteed that values in $P$ are pairwise distinct.

Output

• Print the answer.

Constraints

• $1 \le n \le 20$.
• $1 \le P_i \le 10^{6} $.
• $1 \le L \le R \le 10^{18}$.

Example

Input:

2 5 16
3 5

Output:

5