该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

噜噜的质数模数

题目背景

噜噜最近在研究一台神秘机器的“吸铁”操作。

为了让这台机器运行得更加稳定，噜噜想给它准备一些新的模数。 不过这些模数有一个严格要求：必须是质数。

现在，机器随机给出了一个整数 $x$，噜噜想从所有质数里挑出一个最合适的模数 $p$，使它和 $x$ 的距离尽可能近。这个任务就交给你来完成了。

题目描述

给定一个整数 $x$，你需要找到一个质数 $p$，使得$|p - x|$尽可能小。

如果同时存在两个质数与 $x$ 的距离相同，也就是说在 $x$ 左右两侧等距离各有一个质数，则输出其中较小的那个质数。

输入格式

输入包含多组测试数据。

第一行输入一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行输入一个整数 $x$，表示给定的数。

输出格式

对于每组测试数据，输出一行一个整数，表示与 $x$ 的绝对差值最小的那个质数。 若有多个答案，输出较小的那个。

输入输出样例

输入 #1

6
1
4
10
20
1000000000
31

输出 #1

2
3
11
19
1000000007
31

样例解释

• 当 $x=1$ 时，离它最近的质数是 $2$。
• 当 $x=4$ 时，左右两边最近的质数分别是 $3$ 和 $5$，二者与 $4$ 的距离都为 $1$，因此取较小的 $3$。
• 当 $x=31$ 时，$31$ 本身就是质数，所以答案就是 $31$。

数据范围

• $1 \le T \le 30$
• $1 \le x \le 10^9$