Cho hai số nguyên dương L và R, hãy đếm số lượng số nguyên tố trong đoạn [L, R].

Với R có thể lên đến \(10^12\), không thể sàng Eratosthenes đến R. Thay vào đó, sử dụng sàng phân đoạn (segmented sieve):

1. Sàng các số nguyên tố đến √R (tối đa \(10^6\)).
2. Dùng các số nguyên tố đó để đánh dấu bội số trong đoạn [L, R].

Đầu vào

Một dòng duy nhất chứa hai số nguyên L và R (\(1 \le L \le R \le 10^12, R -L \le 10^6\)).

Đầu ra

Số lượng số nguyên tố trong đoạn [L, R].

Ví dụ

Input:
10 30

Output:
6

Giải thích

Các số nguyên tố: 11, 13, 17, 19, 23, 29.

Ràng buộc & Subtasks