Given an integer N ≤ 10⁴⁰ find the smallest m ≤ N such that m / phi(m) is maximum, where Phi is Euler's totient function.

Input

There are twenty values for N.

N₁
N₂
.
.
.
N₂₀

Output

Output twenty answers, one for each value of N in the input.

m₁
m₂
.
.
.
m₂₀

Example

Input:
10
.
.
Output:
6
.
.