GCD Gap Counting

Little F's mathematics teacher assigned him a homework problem:

Given the values of \(a, b, c, d\), count how many pairs of positive integers \((x, y)\) satisfy all of the following conditions, where \(\gcd(x, y)\) denotes the greatest common divisor of \(x\) and \(y\):</p>

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

Observing that if we write \(x = u\cdot g\) and \(y = (u+1)\cdot g\) with \(u \ge 1\) and \(g \ge 1\), we have \(y-x = g\) and \(\gcd(x,y)=g\) (since \(u\) and \(u+1\) are coprime). The constraints on \(x\) and \(y\) can then be rewritten as:

• \(a \le u\cdot g \le b\),
• \(c \le (u+1)\cdot g \le d\).

Your task is to compute the number of pairs \((x, y)\), or equivalently the number of pairs \((u, g)\), that satisfy these conditions.

inputFormat

The input consists of a single line containing four space-separated integers: \(a\), \(b\), \(c\), and \(d\). It is guaranteed that \(1 \le a \le b \le 10^{12}\) and \(1 \le c \le d \le 10^{12}\).

outputFormat

Output a single integer, the number of positive integer pairs \((x,y)\) satisfying the conditions.

sample

1 10 1 10

17