일반화 윤년

면접 대비

시간 제한8초메모리 제한512 MB

요약

각 테스트마다 약수 목록 A로 정의된 일반화 윤년 규칙을 만족하는 [l, r] 구간의 정수 x 개수를 센다.

문제

보통 서기 $x$ 년이 윤년인지는 다음과 같이 정의된다.

이 정의는 다음과 같이 일반화할 수 있다. 수열 $A_1, \dots, A_n$ 이 주어졌을 때, 서기 $x$ 년이 "일반화 윤년"인지는 다음과 같이 정의한다.

$x$ 가 $A_i$ 의 배수가 되는 가장 작은 $i$ ( $1 \le i \le n$ )에 대해, $i$ 가 홀수이면 일반화 윤년이고 짝수이면 일반화 윤년이 아니다.
그러한 $i$ 가 존재하지 않으면, $n$ 이 홀수일 때 일반화 윤년이 아니고 짝수일 때 일반화 윤년이다.

예를 들어 $A = [400, 100, 4]$ 일 때, 이 $A$ 에 대한 일반화 윤년은 보통의 윤년과 같다.

수열 $A_1, \dots, A_n$ 과 양의 정수 $l, r$ 이 주어진다. $l \le x \le r$ 인 양의 정수 $x$ 가운데 서기 $x$ 년이 $A$ 에 대한 일반화 윤년인 $x$ 의 개수를 구하라.

입력은 최대 50개의 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식으로 주어진다.

n l r
A1
A2
...
An

정수 $n$ 은 $1 \le n \le 50$ 을 만족한다. 정수 $l, r$ 은 $1 \le l \le r \le 4000$ 을 만족한다. 각 $i$ 에 대해 정수 $A_i$ 는 $1 \le A_i \le 4000$ 을 만족한다.

입력의 끝은 세 개의 0으로 이루어진 행으로 나타낸다.

각 데이터 세트마다 답을 한 줄에 출력하라.

예제 1

입력

3 1988 2014
400
100
4
1 1000 1999
1
2 1111 3333
2
2
6 2000 3000
5
7
11
9
3
13
0 0 0

예상 출력