题目描述

薯条哥对 $gcd$ (最大公约数) 很感兴趣, 他会询问你$t$次。

每次询问给出一个大于 $1$ 的正整数 $n$

你是否找到一个数字$m(1 ≤m ≤ n)$，使得 $gcd(n, m)$ 为素数。

输入描述

每个测试文件将包含多组测试数据。

第一行包含一个整数 $T (1 \le T \le 100)$，代表数据组数，每组测试数据描述如下：

在一行输入一个整数$n (2 \le n \le 10^5)$,表示待测的数字。

输出描述

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

如果有多种合法答案，输出任意一个满足条件的数字$m$即可。

样例

输入

2
114
15

输出

57
5