#NDIVPHI. N DIV PHI_N

N DIV PHI_N

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

Input

N1
N2
.
.
.
N20

Output

m1
m2
.
.
.
m20

Example

Input:
10
.
.
Output:
6
.
.