题目描述

给定 $n(1 \leq n \leq 5\times10^5)$ 个整数 $x(2 \leq x \leq 10^7)$，输出 x 的最小质因子。

格式要求

输入格式

第 1 行先输入一个整数 n

接下来 n 行，每行输入一个整数 x

输出格式

输出 n 行，每行一个整数，代表每个 x 对应的最小质因子

样例

3
2
9
12

2
3
2

数据范围与提示

对于 $30\%$ 的数据，$1 \leq n \leq 10^2, 2 \leq x \leq 10^4$

对于 $60\%$ 的数据，$1 \leq n \leq 10^4, 2 \leq x \leq 10^7$

对于 $100\%$ 的数据，$1 \leq n \leq 5\times10^5, 2 \leq x \leq 10^7$