问题描述

定义 $F(x)$ 为整数 $x$ 的最小质因子（即能整除 $x$ 的最小质数）。

给定 $q$ 个查询，每个查询一个整数 $x$，请输出 $F(x)$ 的值。

输入格式

第一行输入一个整数 $q$，表示查询的个数。

接下来 $q$ 行，每行输入一个整数 $x$。

$(1 \le q \le 2\cdot 10^5, \ 2 \le x \le 10^6)$

输出格式

对于每个查询输出一行，表示该整数的最小质因子。

样例输入

5
2
15
10
7
20

样例输出

2
3
2
7
2