#3085. 反质数加强版SAPGAP

内存限制:256 MiB 时间限制:3 Sec

题目描述

先解释一下SAPGAP=Super AntiPrime, Greatest AntiPrime(真不是网络流),于是你就应该知道本题是一个关于反质数(Antiprime)的问题。下面给出反质数的定义:
将一个正整数i的约数个数记为g(i),如g(1)=1,g(2)=2,g(6)=4。
如果对于一个正整数k,对于任意正整数i<k,均有g(k)>g(i),则k被称为反质数。
比如说1,2,4,6,12就是前5个反质数。
现在给定一个N,求N以内最大的反质数。
你一定会认为这道题很简单,你曾经做过好多遍(它就是许许多多竞赛的原题呀),但是这次真的不一样。
 

输入格式

一个正整数N(1≤N≤10100)。
 

输出格式

一个正整数,表示不超过N的最大的反质数。
 

样例

样例输入


			
1000

样例输出


			
840

数据范围与提示

 

HINT

对于5%的测试数据,n≤10000。

对于10%的测试数据,n≤100000。

对于20%的测试数据,n≤109。

对于35%的测试数据,n≤1017。

对于60%的测试数据,n≤1030。

对于100%的测试数据,n≤10100。