题目描述

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

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

例如：

• $36 = 2 \times 2 \times 3 \times 3$，最小质因子是 $2$；
• $49 = 7 \times 7$，最小质因子是 $7$；
• $89 = 89$，最小质因子是 $89$；
• $967217 = 37 \times 26141$，最小质因子是 $37$；

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

说明/提示

数据范围

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

• 对于测试点 1~8：$n \leq 1000$；
• 对于测试点 9~14：$n \leq 10^5$；
• 对于测试点 15~17：$n \leq 10^9$；
• 对于测试点 18~20：$n \leq 10^{12}$；