Coprime Integers

Time limit2sMemory limit512 MB

Summary

Count ordered pairs (x, y) with x in [a, b] and y in [c, d] that share no common factor greater than 1.

Level: Medium7 of 10
Topics: Number theory, Math, Dynamic programming, Prefix sum
Solved: No attempts yet

Problem

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

Input

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).

Output

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

Examples3

Example 1
Input
```
1 5 1 5
```
Expected output
```
19
```
Example 2
Input
```
12 12 1 12
```
Expected output
```
4
```
Example 3
Input
```
1 100 1 100
```
Expected output
```
6087
```