Fișierul intrare/ieșire	intervale.in, intervale.out	Sursă	ad-hoc
Autor	din folclor	Adăugată de	Victor Manz • vmanz
Timp de execuție pe test	0.5 sec	Limită de memorie	42000 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Intervale

Algorel are de rezolvat o noua problema la ora de matematica: trebuie sa raspunda la Q intrebari de forma “cate numere naturale cu exact K divizori primi se afla in intervalul [A,B]?”. Cum matematica nu a fost niciodata punctul sau forte, va cere sa-l ajutati cu un program care sa rezolve rapid problema.

Date de intrare

Fișierul de intrare intervale.in contine pe fiecare din cele cel mult 100 000 de linii ale sale cate trei numere naturale: A, B si K cu semnificatia de mai sus. Acestea sunt separate prin cate un spatiu.

Date de ieșire

În fișierul de ieșire intervale.out vor fi scrise, cate unul pe fiecare rand, raspunsurile la intrebari.

Restricții

• 1 ≤ A < B ≤ 1 000 000

• 0 ≤ K ≤ 1000

• se garanteaza ca pentru 80% din teste 1 ≤ A < B ≤ 100 000

Exemplu

Explicație

2, 3, 4, 5, 7, 8, si 9 au exact un divizor prim,
6 si 10 au cate 2,
nu exista niciun numar cu 3 divizori primi cuprins intre 1 si 10,
1 nu are niciun divizor prim