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

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

В первой строке число $q$ от $1$ до $10^5$. Во второй — $q$ чисел от $2$ до $10^6$.

$q$ чисел через пробел.

Сто тысяч разложений по отдельности — это сто тысяч раз по тысяче шагов. Решето можно немного изменить: пусть оно запоминает не «простое или нет», а сам наименьший простой делитель.