Exclusive Multiples

Version: Phuoc Hung OJ Extended

Problem Statement

You are given four positive integers $L, R, A, B$ with $L \le R$.

An integer $x$ is called an exclusive multiple if it is divisible by exactly one of $A$ and $B$; that is, it is divisible by $A$ or by $B$, but not by both.

Count the exclusive multiples in the interval $[L,R]$.

Input

One line contains four positive integers $L, R, A, B$ separated by spaces.

Output

Print one integer: the number of exclusive multiples in $[L,R]$.

Subtasks

• Subtask 1 (40%): $1 \le L \le R \le 10^6$, $1 \le A,B \le 10^9$.
• Subtask 2 (30%): $1 \le L \le R \le 10^{12}$, $1 \le A,B \le 10^9$.
• Subtask 3 (30%): $1 \le L \le R \le 10^{18}$, $1 \le A,B \le 10^9$.

Examples

Example 1

Input

1 20 4 6

Output

6

Explanation

The valid numbers are $4,6,8,16,18,20$. Number $12$ is divisible by both $4$ and $6$, so it is excluded.

Example 2

Input

10 30 5 10

Output

2

Explanation

The multiples of $5$ are $10,15,20,25,30$. Values $10,20,30$ are also multiples of $10$, leaving only $15$ and $25$.

Example 3

Input

7 9 2 3

Output

2

Explanation

In $[7,9]$, number $8$ is divisible only by $2$ and number $9$ only by $3$, so there are two valid numbers.