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}\)

Example

3 10 20
3 4 5 

5