题目描述

给出若干个数，输出每个数的最小质因子。若本身是素数，就输出它自己。

输入格式

第一行一个整数 q。 第二行 q 个正整数。

输出格式

输出每个数的最小质因子。

4
12 18 25 97

2 2 5 97

数据范围与约定

1≤q≤10$^5$，每个数不超过10$^6$。