Description

Your memory was taken away by the Singer.

Before leaving, the Singer told you that there is a sequence in your memory, and this sequence is a permutation of all integers $x$ with $l \le x \le r$.

After thinking for a moment, the Singer decided to tell you a bit more:

If we define the weight of a sequence as the number of adjacent pairs whose product is a perfect square, then the sequence in your memory is the permutation with the maximum weight among all permutations formed by the integers $x$ with $l \le x \le r$.

The Singer wants you to tell him the weight of the sequence in your memory. Only then will he return your memory to you.

Input Format

One line containing two positive integers $l, r$.

Output Format

One line containing one integer, which is the answer.

2 10

2

Hint

[Sample $1$ Explanation]

One permutation with weight $2$ is $\{8,2,4,9,3,10,7,5,6\}$. In it, $8 \times 2 = 16$ and $4 \times 9 = 36$ are perfect squares. This is also the permutation with the maximum weight among all permutations formed by the integers $x$ with $2 \le x \le 10$.

[Constraints]

This problem uses bundled tests.

Subtask 1 (3 points): $r \le 10$.
Subtask 2 (7 points): $r \le 100$.
Subtask 3 (15 points): $r \le 100000$.
Subtask 4 (11 points): $l = 1$.
Subtask 5 (8 points): $l \le 10$.
Subtask 6 (19 points): $l \le 1000000$.
Subtask 7 (37 points): no special restrictions.

For $100\%$ of the testdata, $1 \le l \le r \le 10^{14}$.

Translated by ChatGPT 5