Viene dato un numero intero $n$ ($2 \le n \le 100000000$). Scrivi un programma per trovare il più piccolo intero positivo $m$ tale che il fattoriale di $m$ sia divisibile per $n$. Qui, per un intero positivo $m$, il fattoriale di $m$ è il prodotto di tutti gli interi da $1$ a $m$.

Input

L'input viene fornito nel file factorial.in. Questo file è composto da una singola riga contenente l'intero $n$.

Output

Il programma deve scrivere il risultato sullo standard output. Stampa una singola riga contenente esclusivamente l'intero $m$.

Esempio

Input 1

10

Output 1

5

Input 2

12

Output 2

4