Se da un número entero $n$ ($2 \le n \le 100000000$). Escribe un programa para encontrar el menor entero positivo $m$ tal que el factorial de $m$ sea divisible por $n$. Aquí, para un entero positivo $m$, el factorial de $m$ es el producto de todos los números enteros desde $1$ hasta $m$.

Entrada

La entrada se proporciona en el archivo factorial.in. Este archivo consta de una sola línea que contiene el entero $n$.

Salida

El programa debe escribir el resultado en la salida estándar. Imprime una sola línea que contenga únicamente el entero $m$.

Ejemplo

Entrada 1

10

Salida 1

5

Entrada 2

12

Salida 2

4