Un entier $n$ ($2 \le n \le 100000000$) est donné. Écrivez un programme permettant de trouver le plus petit entier strictement positif $m$ tel que la factorielle de $m$ soit divisible par $n$. Ici, pour un entier strictement positif $m$, la factorielle de $m$ désigne le produit de tous les entiers de $1$ à $m$.

Entrée

L'entrée est donnée dans le fichier factorial.in. Ce fichier est composé d'une seule ligne contenant l'entier $n$.

Sortie

Le programme doit afficher le résultat sur la sortie standard. Affichez une seule ligne contenant uniquement l'entier $m$.

Exemple

Entrée 1

10

Sortie 1

5

Entrée 2

12

Sortie 2

4