Count Perfect Squares in an Interval

Version: Phuoc Hung OJ Extended

Problem Statement

A positive integer is called a perfect square if it is the square of a positive integer. For example, $1,4,9,16$ are perfect squares.

Given two positive integers $L$ and $R$, count the perfect squares in the interval $[L,R]$. Equivalently, count the integers $x$ such that $L \le x \le R$ and there exists a positive integer $k$ with $x=k^2$.

Input

One line contains two positive integers $L$ and $R$.

Output

Print one integer: the number of perfect squares in $[L,R]$.

Subtasks

• Subtask 1 (20%): $1 \le L \le R \le 10^6$.
• Subtask 2 (30%): $1 \le L \le R \le 10^{12}$.
• Subtask 3 (50%): $1 \le L \le R \le 10^{18}$.

Examples

Example 1

Input

1 10

Output

3

Explanation

The perfect squares in $[1,10]$ are $1=1^2$, $4=2^2$, and $9=3^2$, so the answer is $3$.

Example 2

Input

25 25

Output

1

Explanation

The interval contains only $25$. Since $25=5^2$, exactly one value is a perfect square.

Example 3

Input

999999999999999999 1000000000000000000

Output

1

Explanation

We have $(10^9-1)^2=999999998000000001<999999999999999999$, while $(10^9)^2=10^{18}$. Hence only $10^{18}$ is a perfect square in the given interval.