Factorial (Factorial)

Interview

Time limit0.5sMemory limit1024 MB

Summary

Given n up to 1e8, find the smallest m such that m! is divisible by n.

Level: Medium6 of 10
Topics: Number theory, Math, Binary search, Greedy
Solved: No attempts yet

Problem

An integer n (2 ≤ n ≤ 100000000) is given. Write a program that finds the smallest positive integer m such that the factorial of m is divisible by n. For a positive integer m, the factorial of m is the product of the integers from 1 to m.

Input

This file consists of one line, which contains the integer n.

Output

The program prints the result to standard output. Print one line containing only the integer m.

Examples2

Example 1
Input
```
10
```
Expected output
```
5
```
Example 2
Input
```
12
```
Expected output
```
4
```