Coprime Integers

문제

Given intervals [a, b] and [c, d], count the number of ordered pairs of co-prime integers (x, y) such that a ≤ x ≤ b and c ≤ y ≤ d. Coprime integers have no common factor greater than 1.

입력

The input consists of a single line of four space-separated integers a, b, c, and d. These integers satisfy the bounds (1 ≤ a ≤ b ≤ 10⁷, 1 ≤ c ≤ d ≤ 10⁷).

출력

Print a single integer: the number of coprime pairs (x, y) with a ≤ x ≤ b, c ≤ y ≤ d.