P5438 [XR-2] Memory

> The past is like a handful of dry sand clenched in your hand. You think you are holding it tightly, but it has already slipped away through the gaps between your fingers. Memory is a river that has long since dried up, leaving only scattered pebbles in a lifeless riverbed. — Liu Cixin, *The Three-Body Problem*.

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.

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

One line containing one integer, which is the answer.

[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