#H1036. 最小质因子

最小质因子

题目描述

给定一个正整数 nn,设 n=p1×p2××pkn = p_1 \times p_2 \times \dots \times p_k,其中 pip_i 均为质数,且对 1i<k1 \leq i < kpipi+1p_i \leq p_{i + 1}

给定 nn ,请你计算其 最小质因子 p1p_1

例如:

  • 36=2×2×3×336 = 2 \times 2 \times 3 \times 3,最小质因子为 22
  • 49=7×749 = 7 \times 7,最小质因子为 77
  • 89=8989 = 89,最小质因子为 8989
  • 967217=37×26141967217=37 \times 26141, 最小质因子为 3737

输入描述

第一行 11 个正整数 TT,代表有 TT 组测试数据。

接下来 TT 行,每行 11 个正整数 nn

输出描述

输出共 TT 行,每个 11 个正整数 p1p_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

数据范围

测试点编号 nn\leq
181 \sim 8 10001000
9149 \sim 14 10510^5
151715 \sim 17 10910^9
182018 \sim 20 101210^{12}

对于所有测试点:1T50,1<n10121 \leq T \leq 50,1 < n \leq 10^{12}