最接近的素数

时间限制：1000MS ｜ 空间限制：128MB ｜ 难度：Mid

题目描述

某天童童在手机上参与了一个互动小游戏，与虚拟人物Dr.Panda进行猜数比赛。当屏幕出现一个整数X时，若能比Dr.Panda更快地发出最接近它的素数答案，将会获得一个意想不到的礼物。

例如：当屏幕出现22时，回答应是23；当屏幕出现8时，回答应是7；若X本身是素数，则回答X；若最接近X的素数有两个时，则回答大于它的素数。

输入格式

第一行，一个正整数n，表示要竞猜的整数个数；

接下来的n行，每行一个正整数X。1≤n≤1000000，1≤X≤10000000

输出格式

共n行，每行一个整数，表示与对应X的最接近它的素数。

样例1

输入

4
22
5
18
8

输出

23
5
19
7

数据范围

1≤n≤1000000，1≤X≤10000000。

知识点与难度

• 难度：Mid
• 知识点：数组、埃氏筛/欧拉筛
• 原标签：数组、埃筛和欧筛、AI编程素养集训课、第三讲(Level4)
• GESP定级：3级

测试点分布