互质数

题目描述

尽可能地数下去，早晚会遇到一个质数，虽然没有人知道它们会在哪里出现，但迟早会被发现。

Orange 在最近的CCPC重庆区域赛，遇到了一个关于欧拉函数的题，我们都知道，欧拉函数是一个经典的积性函数，因为对数学的理解不够深刻，Orange竟然记错了积性函数的定义，从而与银牌失之交臂，这实在是太难绷了。

于是，Orange重温了积性函数的定义：对于一个函数 $f$ ，当且仅当 $\gcd(x,y)=1$ 时，满足 $f(xy) = f(x) \times f(y)$ ，那么 $f$ 就是一个积性函数。

现在，Orange 有一个正整数 $n$ ，请你帮他在 $[2, 10^9]$ 内找到一个整数 $m$ 使得 $m$ 和 $n+m$ 对于积性函数 $f$ 满足:

f(m \times (n+m)) = f(m) \times f(n + m)

输入包含多组测试数据，第一行为一个整数 $T$ ，表示测试数据数量，随后每行包含一个整数 $n$ ，表示他给你的数。

数据范围: $T \le 10^3$ $n \le 10^9$

对于每组测试数据，输出一行表示答案。

5
3
3