triprime

Un număr se numește triprim dacă este produsul a trei numere prime distincte. Exemple de numere triprime: $30 = 2 \times 3 \times 5$, $42 = 2 \times 3 \times 7$, $231 = 3 \times 7 \times 11$. Exemple de numere care nu sunt triprime: $77 = 7 \times 11$ (prea puține numere prime în produs), $3003 = 3 \times 7 \times 11 \times 13$ (prea multe numere prime în produs), $18 = 2 \times 3 \times 3$ (numerele prime nu sunt distincte), $10241 = 7 \times 7 \times 11 \times 19$ (prea multe numere prime în produs).

Cerință

Date fiind numerele $A$ și $B$ să se afișeze numărul de numere triprime din intervalul [$A, B$] (inclusiv $A$ și $B$).

Date de intrare

Fișierul de intrare triprime.in conține pe prima linie două numere naturale $A$ și $B$, despărțite printr-un singur spațiu.

Date de ieșire

Fișierul de ieșire triprime.out va conține numărul de numere triprime din intervalul [$A, B$].

Restricții și precizări

• $1 \leq A \leq B \leq 390 \ 000 \ 000$

Exemplul 1

triprime.in

1 50

triprime.out

2

Explicație

Sunt două numere triprime de la $1$ la $50$: $30 = 2 \cdot 3 \cdot 5$ și $42 = 2 \cdot 3 \cdot 7$.

Exemplul 2

triprime.in

50 105

triprime.out

5

Explicație

Sunt cinci numere triprime de la $50$ la $105$: $66 = 2 \cdot 3 \cdot 11$, $70 = 2 \cdot 5 \cdot 7$, $78 = 2 \cdot 3 \cdot 13$, $102 = 2 \cdot 3 \cdot 17$ și $105 = 3 \cdot 5 \cdot 7$.

Exemplul 3

triprime.in

1000 3000

triprime.out

348

Explicație

Sunt $348$ de numere triprime în intervalul [$1 \ 000, 3 \ 000$].