题目描述

给定一个正整数 $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

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}$。