Cerința

Se dau n perechi de numere naturale, x şi k. Verificaţi pentru fiecare număr x dacă este produs de k numere prime distincte.

Date de intrare

Fișierul de intrare eratostene7.in conține pe prima linie numărul n, iar pe următoarele n linii câte o pereche de numere x şi k, separate prin spaţiu.

Date de ieșire

Fișierul de ieșire eratostene7.out va conține pe primele n linii cuvântul DA sau NU corespunzător celei de-a n-a perechi din fişierul de intrare.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• 1 ≤ x ≤ 1.000.000
• 1 ≤ k ≤ 100

Exemplu:

eratostene7.in

3
20 3
30 3
49 2

eratostene7.out

NU
DA
NU

Explicație

Numărul 20 nu este produs de 3 numere prime distincte, 30=2•3•5 este produs de trei numere prime distincte, 49 nu este produs de 2 numere prime distincte.