Cho ~n~ số tự nhiên ~a_1, a_2, ..., a_n~. Hãy xác định xem có bao nhiêu số ~x~ trong đoạn ~[l, r]~ mà ~x~ không chia hết cho số ~a_i~ nào cả.

Input

• Dòng đầu tiên chứa 3 số nguyên dương ~n, l, r \ (1 \leq n \leq 18)~
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n \ (1 \leq a_i \leq 10^9)~

Output

• In ra một số nguyên là đáp số bài toán

  Scoring

• Subtask ~1~ (~30\%~ số điểm): ~1 \leq l \leq r \leq 10^6~

• Subtask ~2~ (~70\%~ số điểm): ~1 \leq l \leq r \leq 10^{18}~

Sample Input

3 10 20
3 4 5

Sample Output

5