Số chính phương đẹp là số chính phương được tạo bởi bình phương của một số nguyên tố đẹp. Số nguyên tố đẹp là số nguyên tố viết từ trái sang phải cũng giống như viết từ phải sang trái (số đối xứng).</p>

Ví dụ:

4 = 2 × 2

9 = 3 × 3

36 = 6 × 6 (loại vì 6 không phải số nguyên tố)

169 = 13 × 13 (loại vì 13 không phải số nguyên tố đẹp)

121 = 11 × 11 (đẹp vì 11 là số nguyên tố đẹp)

Các số như 4, 9, 121 là số chính phương đẹp.

Các số như 36, 169 không phải là số chính phương đẹp.

Yêu cầu:

Cho hai số nguyên dương a và b. Hãy đếm xem trong đoạn [a; b] có bao nhiêu số chính phương đẹp.

Dữ liệu vào:

Đọc từ tệp SOCPDEP.INP gồm hai số nguyên a và b (2 ≤ a ≤ b ≤ 10¹²).

Dữ liệu ra:

Ghi vào tệp SOCPDEP.OUT: Gồm một số là kết quả của bài toán.

Ví dụ:

SOCPDEP.INP</p>

2 8

SOCPDEP.OUT

1

Giải thích: Trong đoạn từ 2 đến 8 có các số là: 2, 3, 4, 5, 6, 7, 8. Trong đó có số 4 = 2×2 mà 2 là số nguyên tố đẹp nên 4 là số chính phương đẹp.

SOCPDEP.INP

13 17

SOCPDEP.OUT

0

Giải thích: Trong đoạn từ 13 đến 17 có các số: 13, 14, 15, 16, 17. Trong đó chỉ có 16 = 4×4 là chính phương, mà 4 không phải số nguyên tố nên 16 không phải số chính phương đẹp.

Ràng buộc:

40% test tương ứng với 40% số điểm của bài, ứng với 2 ≤ a ≤ b ≤ 10³.</p>

30% test tương ứng với 30% số điểm của bài, ứng với 2 ≤ a ≤ b ≤ 10⁵.

30% test tương ứng với 30% số điểm của bài, ứng với 2 ≤ a ≤ b ≤ 10¹².