题目描述

给定一个正整数 n，设 $n = A_1 * A_2 * ... * A_k$ ，其中 $A_i$都是质数，且 $1 \leq i < k ， A_i \leq A_{i+1}$。给定一个正整数 $n$，请你计算其某最小的质因子 $A_{min}$ 。

例如：

• 36 = 2 × 2 × 3 × 3，最小质因子是 2。
• 49 = 7 × 7，最小质因子是 7。
• 89 = 89，最小质因子是 89。
• 9672717 = 37 × 26141，最小质因子是 37。

输入格式

第一行有 1 个整数 T，代表一共有 T 个组数据。 对于接下来的 T 行，每行都有 1 个整数 n。

输出格式

输出 T 行，每行 1 个整数 $A_{min}$ 代表答案。

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

输出样例1

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

数据范围

$T <=100$

• 对于前 8 组数据，均有 $1 < n \leq 1000$
• 对于测试组 9 ~ 14：有 $n < 10^5$
• 对于测试组 15 ~ 17：有 $n < 10^9$
• 对于测试组 18 ~ 20：有 $n < 10^{12}$