==Include(page="template/taskheader" task_id="divprim")==
 
==Include(page="template/raw")==
 
Divizori Primi
 
h2. Cerinta
 
Se doreste aflarea celui mai mare numar natural mai mic sau egal decat un numar N si care are exact K divizori primi.
 
h2. Date de Intrare
 
Prima linie a fisierului de intrare divprim.in contine un numar intreg T reprezentand numarul de teste din fisier. Pe urmatoarele T linii se afla doua numere N si K cu semnificatia de mai sus.
 
h2. Date de Iesire
 
In fisierul divprim.out veti afisa T linii fiecare continand numarul intreg X care satisface propritatile respective sau 0 in cazul in care nu exista un astfel de numar.
 
h2. Restrictii si precizari
 
. 1 <= T <= 100.000
 
. 0 <= K <= 7
 
. 1 <= N <= 1.000.000
 
. 1 nu este numar prim si are 0 divizori primi.
 
h2. Exemplu
 
 
|divprim.in |divprim.out |
 
|3 |9 |
|10 1 |0 |
|10 3 |6 |
|9 2 | |
 
 

==Include(page="template/taskheader" task_id="divprim")==
 
Se doreste aflarea celui mai mare numar natural mai mic sau egal decat un numar $N$ si care are exact $K$ divizori primi.
 
h2. Date de Intrare
 
Prima linie a fisierului de intrare $divprim.in$ contine un numar intreg $T$ reprezentand numarul de teste din fisier. Pe urmatoarele $T$ linii se afla doua numere $N$ si $K$ cu semnificatia de mai sus.
 
h2. Date de Iesire
 
In fisierul $divprim.out$ veti afisa $T$ linii fiecare continand numarul intreg $X$ care satisface propritatile respective sau $0$ in cazul in care nu exista un astfel de numar.
 
h2. Restrictii si precizari
 
* $1 ≤ T ≤ 100.000$
* $0 ≤ K ≤ 7$
* $1 ≤ N ≤ 1.000.000$
* $1$ nu este numar prim si are $0$ divizori primi.
 
h2. Exemplu
 
table(example). |_. divprim.in |_. divprim.out |
| 3
10 1
10 3
9 2
| 9
0
6 |
 
h3. Explicatii
 
$3$ este sigurul divizor prim al lui $9$
Nu exista numar mai mic sau egal cu $10$ care sa aiba $3$ divizori primi, primul astfel de numar fiind $30$
$2$ si $3$ sunt singurii divizori primi ai lui $6$
 
==Include(page="template/taskfooter" task_id="divprim")==

Explicatii
3 este sigurul divizor prim al lui 9 .
Nu exista numar mai mic sau egal cu 10 care sa aiba 3 divizori primi, primul astfel de numar fiind 30 .
2 si 3 sunt singurii divizori primi ai lui 6 .
==Include(page="template/taskfooter" task_id="divprim")==

791