fact

Pentru un număr natural nenul, definim factorialul său ca fiind produsul tuturor numerelor naturale nenule mai mici sau egale decât el şi îl notăm $N!$ (adică $N!=1 \cdot 2\cdot \ldots \cdot N$). Pentru o bază de numeraţie $B$ şi un număr natural nenul $N$, se cere determinarea ultimei cifre nenule a scrierii în baza $B$ a lui $N!$.

Cerinţă

Se citesc $5$ perechi de forma $(N_i,B_i)$, unde $1 \leq i \leq 5$. Pentru fiecare din cele $5$ perechi citite, aflaţi ultima cifră nenulă a scrierii în baza $B_i$ a factorialului numărului $N_i$.

Date de intrare

Fişierul de intrare fact.in conţine $5$ linii, pe fiecare dintre ele fiind scrise câte două numere naturale nenule $N_i$ şi $B_i$, scrise în baza $10$, despărţite printr-un spaţiu.

Date de ieșire

Fişierul de ieşire fact.out va conţine $5$ linii. Pe linia $i$ se va afla cifra corespunzătoare unei perechi $(N_i,B_i)$, citită de pe linia $i$ din fişierul de intrare.

Restricții și precizări

• $1 \leq N_i \leq 1 \ 000 \ 000$, pentru $1 \leq i \leq 5$;
• $2 \leq B_i \leq 36$, pentru $1 \leq i \leq 5$;
• în cazul în care $B_i > 10$, cifrele mai mari decât $9$ vor fi reprezentate prin litere mari ale alfabetului englez $(10=’A’, 11=’B’,…,35=’Z’)$;
• un test va fi punctat doar dacă toate cele $5$ rezultate cerute sunt corecte.

Exemplu

fact.in

5 10
7 10
7 20
8 16
9 8

fact.out

2
4
C
8
6

Explicație

$5!=120$, în baza $10$, deci ultima cifră nenulă este $2$;
$7!=5040$, în baza $10$, deci ultima cifră nenulă este $4$;
$7!=CC0$, în baza $20$, deci ultima cifră nenulă este $C$;
$8!= 9D80$, în baza $16$, deci ultima cifră nenulă este $8$;
$9!=1304600$, în baza $8$, deci ultima cifră nenulă este $6$.