Given an integer N <= 10⁴⁰ find the smallest m <= N such that m/phi(m) is maximum.

Input

N₁
N₂
.
.
.
N₂₀

Output

m₁
m₂
.
.
.
m₂₀

Example

Input:
10
.
.

Output:
6
.
.