Antiprime Numbers

Time limit3sMemory limit512 MB

Summary

Given n up to 2e9, find the largest highly composite number (one with more divisors than every smaller positive integer) that does not exceed n.

Level: Medium6 of 10
Topics: Number theory, Brute force, Combinatorics, Math
Solved: No attempts yet

Problem

A positive integer is called an antiprime (also known as a highly composite number) if it has strictly more divisors than every positive integer smaller than it. For example, $1, 2, 4, 6, 12, 24$ are all antiprimes.

Given an integer $n$ , write a program that finds the largest antiprime that is not greater than $n$ .

Input

The first line contains a single integer $n$ ( $1 \le n \le 2000000000$ ).

Output

Print, on a single line, the largest antiprime that is not greater than $n$ .

Examples4

Example 1
Input
```
1000
```
Expected output
```
840
```
Example 2
Input
```
1
```
Expected output
```
1
```
Example 3
Input
```
2
```
Expected output
```
2
```
Example 4
Input
```
3
```
Expected output
```
2
```