Factorial

Ce poate fi mai interesant decât factorialele și zerourile! Factorialul unui număr natural nenul $X$ este produsul numerelor de la $1$ la $X$ și se notează $X!$. Mai întâi ai vrea să aflii pentru mai multe numere cu câți de $0$ se termină factorialul lor. Apoi, ai vrea să aflii pentru fiecare număr $X$, care este cel mai mic număr natural nenul $k$ astfel încât $k!$ să se termine cu $X$ de $0$. Dacă nu există un astfel de număr, se va afișa $-1$.

Cerință

• Determinați pentru fiecare număr $X$, cu câți de $0$ se termină $X!$.
• Determinați pentru fiecare număr $X$, cel mai mic număr natural nenul $k$, astfel încât $k!$ să se termine cu $X$ de $0$.

Date de intrare

Pe prima linie a fișierului de intrare factorial.in se găsesc două numere întregi, $C$, reprezentând cerința și $N$ reprezentând numărul de numerele. Pe următoarele $N$ linii se va regăsi câte un număr natural $X$ cu semnificația din enunț.

Date de ieșire

În fișierului de ieșire factorial.out se vor găsi $N$ numere, pe linii diferite, reprezentând în ordine răspunsul pentru fiecare $X$. Dacă $C=1$ se va afișa
cu câți de $0$ se termină $X!$. Dacă $C=2$ se va afișa cel mai mic număr natural nenul $k$, astfel încât $k!$ să se termine cu $X$ de $0$ sau $-1$ dacă nu există.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$;
• $1 \leq X \leq 10^9$;

Pentru $C=1$ și $1\leq X \leq 20$ există câte un test în valoare de $1$ punct pentru fiecare $X$.
Pentru $C=2$ și $1\leq X \leq 5$ există câte un test în valoare de $1$ punct pentru fiecare $X$.

Exemplul 1

factorial.in

1 5
5 
25 
100
27500 
1000000000

factorial.out

1
6
24
6873
249999998

Explicație

$5!=120$, deci se termină într-un singur $0$. Prin urmare, răspunusul pentru $X=5$ este $1$.

Exemplul 2

factorial.in

2 5
5 
25 
100
27500 
1000000000

factorial.out

-1
105
405
110005
4000000015

Explicație

Nu există niciun număr $k$ pentru care $k!$ să se termine cu $5$ de $0$. Prin urmare, se afișează $-1$. $105!$ se termină cu $25$ de $0$.