407264: GYM102739 F Саша опять делает задачу про простые числа
Description
Во время карантина Саша почти всё время сидела дома и заметила, что стала слишком мало двигаться. Чтобы контролировать свою активность, она купила фитнес-трекер и теперь каждый вечер смотрит, сколько шагов нашагала за день.
Однако решение одной проблемы сразу повлекло за собой другую: дело в том, что Саше нравятся далеко не все числа, так что в некоторые вечера она бывает не довольна результатом за день, даже если он был достаточно продуктивным. А именно, из всех натуральных чисел Саше нравятся только простые числа и степени двойки (т.к. остальные числа недостаточно математичные).
Но и для этой проблемы у Саши есть решение: теперь она смотрит показания трекера за некоторое время до сна, а потом совершает променад по квартире, пока число шагов не становится математичным.
Разумеется, Саша не помнит наизусть все математичные числа, так что просит вас помочь ей находить наименьшее подходящее математичное число.
Входные данныеВ первой строке дано одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — число дней, в которые Саша носила фитнес-трекер.
Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$ ($$$0 \le a_i \le 10^7$$$) — вечерние показания трекера в течение $$$n$$$ дней.
Выходные данныеВыведите $$$n$$$ чисел: для каждого $$$a_i$$$ ближайшее математичное число, не меньшее его.
Система оценки$$$$$$\begin{array}{|c|c|c|c|c|} \hline \text { Подзадача } & \text { Баллы } & \text { Ограничения } & \text { Оценка } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text { подзадача } & \\ \hline 1 & 25 & n \le 1000, a_i \le 1000 & \text { подзадача } & \\ \hline 2 & 17 & n \le 1000 & \text { подзадача } & 1 \\ \hline 3 & 17 & a_i \le 1000 & \text { подзадача } & 1 \\ \hline 4 & 41 & \text{ Без дополнительных ограничений } & \text { подзадача } & 1, 2, 3 \\ \hline \end{array}$$$$$$
ПримерВходные данные5 2020 1023 0 101 10000Выходные данные
2027 1024 1 101 10007