a12_0001

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А) заменить(v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.

Б) нашлось(v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь».

Дана программа для Редактора:

НАЧАЛО
ПОКА нашлось(>1) ИЛИ нашлось(>2) ИЛИ нашлось(>0)
   ЕСЛИ нашлось(>1)
      ТО заменить(>1,22>)
   КОНЕЦ ЕСЛИ
   ЕСЛИ нашлось(>2)
      ТО заменить(>2,2>)
   КОНЕЦ ЕСЛИ
   ЕСЛИ нашлось(>0)
      ТО заменить(>0,1>)
   КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с символа «>», а затем содержащая 39 цифр «0», n цифр «1» и 39 цифр «2», расположенных в произвольном порядке.

Определите наименьшее значение n, при котором сумма числовых значений цифр строки, получившейся в результате выполнения программы, является простым числом.