exponent

Se consideră un şir $a=(a_1, a_2, \dots ,a_n)$ de $n$ numere naturale strict pozitive şi un număr natural $d$, de asemenea strict pozitiv.

Cerinţă

Scrieţi un program care calculează numărul natural $k$, maxim, cu proprietatea că produsul tuturor numerelor din şirul $a$ este divizibil cu $d^k$.

Date de intrare

Pe prima linie a fişierului exponent.in sunt scrise numerele naturale $n$ şi $d$, separate printr-un spaţiu. Pe următoarea linie se găsesc cele $n$ elemente ale şirului dat, separate prin câte un spaţiu.

Date de ieșire

Fişierul exponent.out conţine o singură linie pe care este scris numărul $k$.

Restricții și precizări

• $1 \leq n \leq 30 \ 000$
• $1 \leq a_i \leq 32 \ 000, i=1,2, \dots n$
• $2 \leq d \leq 32 \ 000$

Exemplul 1

exponent.in

5 12
200 66 18 3 8

exponent.out

4

Exemplul 2

exponent.in

3 7
33 50 24

exponent.out

0