Không chia hết

Cho \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\). Hãy xác định xem có bao nhiêu số nguyên \(x\) trong đoạn \([l, r]\) mà \(x\) không chia hết cho bất kỳ số \(a_i\) nào.

Input

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

Output

• In ra một số nguyên duy nhất là đáp án của bài toán.

Example

3 10 20
3 4 5

5

Scoring

• Subtask 1 (30% số điểm): \(1 \le l \le r \le 10^6\).
• Subtask 2 (70% số điểm): \(1 \le l \le r \le 10^{18}\).