题目描述

某天童童在手机上参与了一个互动小游戏，与虚拟人物Dr.Panda进行猜数比赛。当屏幕出现一个整数X时，若能比Dr.Panda更快地发出最接近它的素数答案，将会获得一个意想不到的礼物。 例如：当屏幕出现22时，回答应是23；当屏幕出现8时，回答应是7；若X本身是素数，则回答X；若最接近X的素数有两个时，则回答大于它的素数。

输入格式

第一行，一个正整数n，表示要竞猜的整数个数； 接下来的n行，每行一个正整数X。1≤n≤1000000, 1≤X≤10000000

输出格式

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

4 
22 
5 
18 
8

23 
5 
19 
7