寻找暗数

余波累加完了，但Echo-0的第三层加密还在等着——最深的，最隐秘的。

"暗数。"Echo说，"不是质数，不是合数，是……反质数。"

"反质数？"

"对。"她说，"约数个数比所有比它小的数都多。比如12——约数有1,2,3,4,6,12，共6个。比12小的数，约数个数都不超过6。"

"那12是反质数？"

"是。"Echo说，"反质数是加密的好材料——约数多，意味着能被很多方式分解，难以逆向破解。"

"我们要找暗数？"

"对。"你说，"给定$n$，找不超过$n$的最大反质数。"

"咋找？"

"质因数分解。"你说，"反质数的质因子一定是连续的——2,3,5,7……而且指数递减。"

"为啥？"

"因为要约数个数多，质因子要小，指数要均匀。"你说，"用DFS枚举所有可能的指数组合，算约数个数。"

"第47个暗数。"你说，"……是45360。"

"45360？"

"对。"你说，"约数个数100个。"

"100个？"

"对。"你说，"100种分解方式——100种密码。"

CC把45360刻在金属手臂上——歪歪扭扭的数字。

"刻这干啥？"

"密码。"她说，"我记性好，但怕忘。"

"你记性不好。"

"对。"她说，"所以我刻下来。"

Echo看着那个数字——45360——像某种图腾，某种信仰。

"以前Echo-0也刻过数字。"她说，"在矿区的墙壁上。"

"刻的啥？"

"47。"她说，"只有47。"

题目描述

给定$n$，求不超过$n$的最大反质数。反质数定义为：约数个数严格大于所有比它小的正整数。

输入格式

一个整数$n$。

输出格式

不超过$n$的最大反质数。

输入样例

5

输出样例

4

提示

• 反质数的质因子一定是连续质数，且指数递减。
• 用DFS枚举指数组合。
• 约数个数公式：$\prod (e_i+1)$。