На уроке математики учительница попросила каждого ученика предложить свое множество счастливых чисел. Будучи без ума от теории чисел, Петя сразу же заявил, что простые числа — это его счастливые числа. Вася оказался оригинальнее, он сказал, что число t для него счастливое, если и только если оно может быть представлено в виде:
t = a2 + b2, где
a, b — произвольные положительные целые числа.
Теперь мальчики решили выяснить сколько дней на отрезке [l, r] (l ≤ r) подходят для парного программирования. Они решили, что день i (l ≤ i ≤ r) подходит для парного программирования, если и только если i является счастливым числом как для Пети, так и для Васи. Помогите мальчикам найти количество таких дней на отрезке [l, r].
Выходные данные
Выведите единственное число — количество дней в отрезке [l, r], которые подходят для парного программирования.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5
|
1
|
|
2
|
6 66
|
7
|