所有的 Yandex 开发人员都有自己喜欢的放松方式。通常他们会玩桌上足球、乒乓球或棋盘游戏，但 Yasha 的小组发明了一种他们自己的纸牌游戏来消磨闲暇时光。

游戏开始时，桌上有 $n$ 张写有正整数的纸牌，白板上写着一个正整数 $M$（起始数字）。两名玩家轮流进行操作。在每次操作中，玩家从桌上取走一张纸牌，擦掉白板上的数字，并写下白板上原有的数字除以纸牌上数字的整数商。操作完成后，所使用的纸牌将从桌上移走。如果一名玩家操作后白板上的数字变为 $0$，则该玩家输掉比赛。

Yasha 是小组中最年轻的成员，所以他总是第二个行动，他认为这可能不公平。为了验证他的假设，他详细研究了这个游戏，现在他知道了卡片上的所有数字 $a_1, a_2, \dots, a_n$ 以及起始数字 $M$ 的取值范围 $L$ 和 $R$。

请帮助 Yasha 计算有多少个满足 $L \le M \le R$ 的整数 $M$，使得如果游戏以白板上写着 $M$ 开始，在双方都采取最优策略的情况下，Yasha 能获胜。

输入格式

输入包含三行。

第一行包含一个整数 $n$：游戏开始时桌上的纸牌数量（$2 \le n \le 10$）。

第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, a_n$：纸牌上写的数字（$1 \le a_i \le 1000$）。

第三行包含两个整数 $L$ 和 $R$：起始数字 $M$ 的边界（$1 \le L \le R \le 10^{18}$，$R < a_1 \cdot a_2 \cdot \dots \cdot a_n$）。

输出格式

输出一个整数：在 $[L, R]$ 范围内，使 Yasha 获胜的 $M$ 的个数。

样例

输入 1

3
1 2 1
1 1

输出 1

1

输入 2

3
2 3 5
1 10

输出 2

2