003 - 一般化うるう年

時間制限 8 秒 / メモリ制限 256 MB / 得点 20 / x 29 /


TLE
8sec
MLE
256MB
得点
20

Problem

通常,西暦 x 年がうるう年か否かは以下のように定義されている.

  1. x が 400 の倍数であれば,うるう年である.
  2. そうでないとき,x が 100 の倍数であれば,うるう年ではない.
  3. そうでないとき,x が 4 の倍数であれば,うるう年である.
  4. そうでないとき,うるう年ではない.

これは次のように一般化できる.ある数列 A1, ..., An について,西暦 x 年が "一般化うるう年" であるか否かを以下のように定義する.

  1. xAi の倍数であるような最小の i (1 ≤ i ≤ n) について,i が奇数であれば一般化うるう年であり,偶数であれば一般化うるう年ではない.
  2. そのような i が存在しないとき,n が奇数であれば一般化うるう年ではなく,偶数であれば一般化うるう年である.

例えば A = [400, 100, 4] のとき,この A に対する一般化うるう年は通常のうるう年と等価になる.

数列 A1, ..., An と正の整数 l, r が与えられるので.l ≤ x ≤ r なる正の整数 x のうち,西暦 x 年が A に対する一般化うるう年であるような x の個数を答えよ.

Input

入力は最大で 50 個のデータセットからなる.各データセットは次の形式で表される.

n l r A1 A2 ... An

整数 n1 ≤ n ≤ 50 を満たす.整数 l,r1 ≤ l ≤ r ≤ 4000 を満たす.各 i に対し整数 Ai1 ≤ Ai ≤ 4000 を満たす.

入力の終わりは 3 つのゼロからなる行で表される.

Output

各データセットについて,答えを 1 行で出力せよ.

Sample Input

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

Output for the Sample Input

7
1000
2223
785