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

给定 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 \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}；

素数