Cho dãy số nguyên dương ~A~ có ~N~ phần tử và hai số nguyên dương ~L, R~. Hãy đếm số lượng số nguyên từ ~L~ đến ~R~ chia hết cho ít nhất một phần tử trong ~A~.

Input

Gồm nhiều bộ test, mỗi bộ test có dạng

• Dòng đầu tiên chứa ba số nguyên ~N, L, R~ ~(1 \leq N \leq 20, 1 \leq L \leq R \leq 10^{18})~.
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \dots, A_N~ ~(1 \leq A_i \leq 10^9)~.

Output

In ra trên một dòng số lượng số nguyên thỏa mãn điều kiện đề bài.

Scoring

• Subtask 1 ~(30\%)~: ~N = 2~.
• Subtask 2 ~(30\%)~: ~N \leq 15~.
• Subtask 3 ~(40\%)~: Không có ràng buộc gì thêm.

Sample Input

1 293 784
1
1 255 734
2
2 579000 987654
1 2
2 1 1000000000
2 3

Sample Output

492
240
408655
666666667