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

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

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

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

$$$$$$\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}$$$$$$