1425: Nineteen

内存限制：32 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：17 解决：11

题目描述

如果一个数字只包含数字4和7，那么这个数就是幸运数字
如果一个数字的所有前缀以及翻转后的所有前缀都是质数或者为1，那么这个数字就代表着绝望
给你一个数字n，求出≤n最大的一个象征绝望的数字


会有大量的询问，且n的范围也非常的大！而你的程序却必须在1秒内得出超过十万组询问的答案，所以我猜你可能会比较绝望？
不过说到绝望，我就想到孙悟空被压在五行山下500年的那种绝望，今年下半年，中美合拍的西游记即将正式开机，我将继续扮演美猴王孙悟空这一角色
我会用美猴王艺术形象努力创造一个正能量的形象，文体两开花，弘扬中华文化，希望大家能多多关注。

输入

多组测试数据
每组测试数据为一个整数n（2≤n≤138888）
可能会有100000组以上的数据

输出

输出满足≤n，最大的象征绝望的数字

样例输入 复制 

5
6
7
22

样例输出 复制 

5
5
7
17

提示

PS：什么是前缀和翻转后的前缀？举个例子就明白了
54318的前缀有5个：54318, 5431, 543, 54, 5，翻转后前缀为：8, 81, 813, 8134, 81345

来源/分类