407264: GYM102739 F Саша опять делает задачу про простые числа

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Саша опять делает задачу про простые числаограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Во время карантина Саша почти всё время сидела дома и заметила, что стала слишком мало двигаться. Чтобы контролировать свою активность, она купила фитнес-трекер и теперь каждый вечер смотрит, сколько шагов нашагала за день.

Однако решение одной проблемы сразу повлекло за собой другую: дело в том, что Саше нравятся далеко не все числа, так что в некоторые вечера она бывает не довольна результатом за день, даже если он был достаточно продуктивным. А именно, из всех натуральных чисел Саше нравятся только простые числа и степени двойки (т.к. остальные числа недостаточно математичные).

Но и для этой проблемы у Саши есть решение: теперь она смотрит показания трекера за некоторое время до сна, а потом совершает променад по квартире, пока число шагов не становится математичным.

Разумеется, Саша не помнит наизусть все математичные числа, так что просит вас помочь ей находить наименьшее подходящее математичное число.

Входные данные

В первой строке дано одно целое число $$$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 

加入题单

上一题 下一题 算法标签: