题目描述

给定一个正整数 $n$，设 $n = p_1 \times p_2 \times ... p_k$，其中 $p_i$ 均为质数，对 $1 \le i < k，p_i \le p_{i+1}$。

给定 $n$，请你计算其最小的质因子 $p_1$。

例如：

• $36=2×2×3×3$，最小质因子是 $2$

• $49=7×7$，最小质因子是 $7$

• $89=89$，最小质因子是 $89$

• $967217=37×26141$，最小质因子是 $37$

输入格式

第一行 $1$ 个整数 $T$，代表有 $T$ 组数据。

接下来 $T$ 行，每行 $1$ 个整数 $n$。

输出格式

输出 $T$ 行，每行 $1$ 个整数 $p_1$ 代表答案。

样例

14 
36 
2 
3 
49 
81 
35 
12 
89 
16
100 
967217 
917597 
185971 
43607027731 

2 
2 
3 
7 
3 
5 
2 
89 
2 
2 
37 
571 
185971 
43607027731

提示

数据范围

对于所有数据，$1 \le T \le 50，1 < n \le 10^{12}$

对于测试点 $1$~$8$：$n \le 1000$

对于测试点 $9$~$14$：$n \le 10^5$

对于测试点 $15$~$17$：$n \le 10^9$

对于测试点 $18$~$20$：$n \le 10^{12}$