Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
заменить(v, w)
нашлось(v)
Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.
Дана программа для Редактора:
ПОКА нашлось(10)
ЕСЛИ нашлось(10) ТО
заменить(10, 001)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось(1)
ТО заменить(1, 01)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
На вход приведённой программы поступает строка, состоящая из 1 и следующими за ней N нулями (N – натуральное число).
Найдите минимальное значение N, при котором длина строки будет простым числом большим 1000000.