Gennady and Artem are discussing solutions of different problems. Gennady told Artem about a number theory problem he solved the day before. One of steps to solve the problem was to calculate the least common multiple (LCM) of all integers from 1 to n, inclusive. That problem inspired Gennady to come up with another problem about LCM's.

Given n, find the greatest m that \(m \le n\) and: \(LCM(1, 2, \ldots, n) = LCM(m, m + 1, \ldots, n)\)

We have no doubt Artem will solve the problem, but will you?

You can find the definition of LCM here.

Input format

The only line of the input contains one integer n.

Output format

Print the greatest integer m satisfying the given conditions.

Constraints

• \(1 \le n \le 10^{15}\)