Задание №44907 ЕГЭ Информатике

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

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

ПОКА нашлось (222) ИЛИ нашлось (999)
    заменить (222, 9)
    заменить (999, 22)
КОНЕЦ ПОКА

Известно, что начальная строка состоит более чем из 139 цифр 2 и не содержит других символов. В ходе работы алгоритма получилась строка, содержащая одну цифру 2 и одну цифру 9. Укажите минимальную возможную длину входной строки.