Наименьший простой делитель

1100 мс · 256 МБ · всё или ничего

Для каждого из $q$ чисел выведите его наименьший простой делитель.

В первой строке — число запросов $q$ ( $1 \le q \le 10^5$ ).

В следующей строке — $q$ чисел $x_i$ ( $2 \le x_i \le 10^7$ ).

Для каждого числа выведите его наименьший простой делитель, через пробел.

ввод

3
2 12 97

вывод

2 2 97

ввод

1
9999991

вывод

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.