Under construction

Still being built. Things may change

Computational ethnography

Interview

Time limit1sMemory limit512 MB

Summary
Count the numbers from A to B whose digit reversal is also a perfect square, where both the number and its reversal are squares and the reversal has no leading zero.
Level

Easy3 of 10

Topics
Brute force, Math
Solved
No attempts yet

Problem

The natives of Island L write numbers backwards: the most significant digit of a number is written last. For example, 144144 is written as 441441.

Petya, a novice ethnographer and mathematician, studies square numbers and the culture of Island L. He found that some numbers are perfect squares both when read normally and when read the way the natives write them. For example, 144=122144 = 12^2, and the native form 441=212441 = 21^2. Petya calls such numbers interesting.

Petya wants to know how many interesting numbers lie between AA and BB, inclusive.

Input

The first line contains the integer AA. The second line contains the integer BB. (1≤A≤B≤10111 \le A \le B \le 10^{11})

Output

Print the number of interesting numbers from AA to BB.

Hint

In the first input, the interesting numbers are 11, 44, 99, 121121, 144144, 169169, 441441, 484484, 676676, and 961961. The natives do not write leading zeros, so 100100 is not interesting.

Examples1

  1. Example 1

    Input
    1
    1000
    
    Expected output
    10