시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 51 26 17 62.963%

문제

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 ≤ 107, 1 ≤ c ≤ d ≤ 107).

출력

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

예제 입력 1

1 5 1 5

예제 출력 1

19

예제 입력 2

12 12 1 12

예제 출력 2

4

예제 입력 3

1 100 1 100

예제 출력 3

6087