小红的因子
题号：NC262021
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红拿到了一个正整数n，她希望找到n的一个最小因子p，满足p*p>n。你能帮帮她吗？
一共有t组询问。

输入描述:

第一行输入一个正整数t，代表询问的次数。
接下来的t行，每行输入一个正整数n。
1\le t \le 10
2\leq n \leq 10^{12}

输出描述:

满足条件的最小因子。
示例1

输入

复制 
2
36
37

输出

复制 
9
37