思路：数论

所有大于1的合数均可以表示为若干个素数的积，即$x=p_{1}^{k_1}*p_{2}^{k_2}*...*p_{n}^{k_n}$

所以我们只需要找到$x$的一个素因子$k$，那么答案即为$x/k$

由于$n$最大为$10^5$，所以我们只需要筛一次素数，然后再判断即可。

题目描述

小乖对 $gcd$ (最大公约数) 很感兴趣, 他会询问你$t$次。 每次询问给出一个大于 $1$ 的正整数 $n$, 你是否找到一个数字$m(2 ≤m ≤ n)$，使得 $gcd(n, m)$ 为素数.

注：原题为给出任意解，本题中请给出最小值作为答案

输入描述

每个测试文件将包含多组测试数据,每组测试数据的第一行包含一个整数 $k (2 ≤ k ≤ 10^5)$, 表示有$k$ 个待测数字.接下来 $k$ 行,每行包含一个整数$n (2 ≤ n ≤ 10^9)$,表示待测的数字.

输出描述

对于每一组测试数据, 在一行上输出一个整数，代表数字 $m$。

示例 1

输入

2
114
15

输出

2
3