Description

小 F 的数学老师 H 老师给小 F 留了一道数学作业。

给定 $a,b,c,d$ 的值，求有多少正整数对 $(x,y)$ 满足以下所有条件。这里，$\gcd(x,y)$ 表示 $x$ 和 $y$ 的最大公约数。

• $x \le y$。
• $a \le x \le b$。
• $c \le y \le d$。
• $y-x=\gcd(x,y)$。

小 F 觉得这个作业实在是太过愚蠢了，信心满满地写满了暴力，结果发现 $a,b,c,d \le 10^{12}$。你是作业帮，你需要帮小 F 完成作业。

Input Format

一行四个正整数 $a,b,c,d$，表示 $x$ 和 $y$ 取值的左右边界。

Output Format

一行一个正整数，表示答案。

2 5 3 7

7

1 100 1 100

382

114 514 191 9810

2433

21899 314099 61699 104699

493292

Hint

样例解释 #1

满足条件的 $(x,y)$ 如下所示：

• $(2,3)$
• $(2,4)$
• $(3,4)$
• $(3,6)$
• $(4,5)$
• $(4,6)$
• $(5,6)$

数据范围

对于 $100\%$ 的数据，保证 $1 \le a \le b \le 10^{12}$，$1 \le c \le d \le 10^{12}$。