Counting Square Roots by Residue Class - EP1

Version: Phuoc Hung OJ Extended

Problem Statement

You are given four integers $L,R,M,r$ with $0 \le r < M$.

Count the positive integers $k$ satisfying both

and

Input

One line containing four integers $L,R,M,r$.

Output

Print one integer: the number of positive integers $k$ satisfying both conditions.

Subtasks

• Subtask 1 (25 points): $R \le 10^6$.
• Subtask 2 (35 points): the integer-root interval that must be considered has length at most $10^6$.
• Subtask 3 (40 points): $1 \le L \le R \le 10^{18}$, $1 \le M \le 10^9$, $0 \le r < M$.

Examples

Example 1

Input

1 30 2 0

Output

2

Explanation

The positive roots whose squares lie in $[1,30]$ are $1,2,3,4,5$. Among them, 2 and 4 are congruent to 0 modulo 2, so the answer is 2.

Example 2

Input

10 100 2 1

Output

3

Explanation

The square condition gives $4 \le k \le 10$. The odd values in this interval are 5, 7, and 9, so the answer is 3.

Example 3

Input

1 100 3 1

Output

4

Explanation

For $1 \le k \le 10$, the values congruent to 1 modulo 3 are 1, 4, 7, and 10. Hence the answer is 4.

Example 4

Input

50 80 5 0

Output

0

Explanation

Only $k=8$ has its square in $[50,80]$, but $8 \bmod 5=3$, so no value is valid.

Example 5

Input

999998000001 1000000000000 1000000 0

Output

1

Explanation

The boundary roots are 999999 and 1000000. Only 1000000 is congruent to 0 modulo 1000000, so the answer is 1.