Factorii invizibili

Se dau două numere naturale $n$ și $k$. Considerăm produsul tuturor numerelor naturale de la $1$ la $n$, notat $n!$.

Vom numi puterea lui $k$ în $n!$ cel mai mare număr natural $p$ pentru care $k^p$ divide $n!$.

Avem două tipuri de cerințe:

1. Cerința de tip 1: Determinați cel mai mare număr $p$ cu proprietatea că $k^p \mid n!$.
2. Cerința de tip 2: Determinați cel mai mic număr $m \ge 1$ pentru care $k^n \mid m!$.

Date de intrare

Fișierul factori.in conține pe prima linie un număr natural $t$ care precizează cerința de rezolvat. Pe a doua linie se vor afla numerele $n$ și $k$, cu semnificația de mai sus, separate prin spațiu.

Date de ieșire

Fișierul factori.out va conține un singur număr natural reprezentând valoarea $p$, dacă $t = 1$ respectiv valoarea $m$, dacă $t = 2$.

Restricții și precizări

• $1 \le t \le 2$
• $1 \le n \le 10^9$
• $2 \le k \le 10^4$
• Se garantează că $m \le 10^{18}$.

Exemplul 1

factori.in

1
28 26

factori.out

2

Explicație

$26 = 2 \cdot 13$.
Factorialul $28!$ conține $25$ factori $2$ și $2$ factori $13$, deci:

Exemplul 2

factori.in

2
28 26

factori.out

338

Explicație

Căutăm cel mai mic $m$ pentru care $k^n \mid m!$.
Prin calcul, rezultă $m = 338$.