题目内容

在密码学中，常常需要用到一类特殊的整数，称为「本原数」：一个大于 1 的正整数，如果它只能被 1 和自身整除，则称其为本原数。

现在，对于给定的整数 x，请你找出与 x 绝对差值最小的本原数。如果左右两侧各存在一个等距的本原数，请输出较小的那个。

数据范围：测试数据组数 T 不超过 30，每次询问的 x 满足 $1 \le x \le 10^9$。

输入描述

第一行包含一个整数 $T$（$1 \le T \le 30$），表示测试数据组数。 接下来 $T$ 行，每行包含一个整数 $x$（$1 \le x \le 10^9$），代表一次询问。

输出描述

对于每组询问，输出一行一个整数，表示距离 $x$ 最近的本原数。

样例1

输入

3
2
1
6

输出

2
2
5

说明

• 对于 $x = 2$：2 自身就是本原数，因此答案为 2。
• 对于 $x = 1$：1 不是本原数，距离 1 最近的本原数是 2（距离为 $1$），因此答案为 2。
• 对于 $x = 6$：左右最近的本原数分别是 5 和 7，距离均为 $1$。根据规则，等距离时取较小的本原数 5，因此答案为 5。

样例2

输入

2
14
1000

输出

13
997

说明

• 对于 $x = 14$：14 不是本原数，左右最近的本原数是 13（距离 $1$）和 17（距离 $3$），最小距离的本原数是 13，因此答案为 13。
• 对于 $x = 1000$：1000 附近的本原数有 997（距离 $3$）和 1009（距离 $9$），最近的是 997，因此答案为 997。

样例3

输入

1
1000000000

输出

1000000007

说明

• 对于 $x = 1000000000$：该数不是本原数。向左寻找，最近的本原数是 999999937，距离为 $63$；向右寻找，最近的本原数是 1000000007，距离为 $7$。最近的是 1000000007，因此答案为 1000000007。