На уроке математики учительница попросила каждого ученика предложить свое множество счастливых чисел. Будучи без ума от теории чисел, Петя сразу же заявил, что простые числа — это его счастливые числа. Вася оказался оригинальнее, он сказал, что число t для него счастливое, если и только если оно может быть представлено в виде:

Теперь мальчики решили выяснить сколько дней на отрезке [l, r] (l ≤ r) подходят для парного программирования. Они решили, что день i (l ≤ i ≤ r) подходит для парного программирования, если и только если i является счастливым числом как для Пети, так и для Васи. Помогите мальчикам найти количество таких дней на отрезке [l, r].