Маленькая Элизабет любит играть со строками. У нее есть строка длины n, полностью состоящая из букв «a». Она делает со строкой следующие действия:
- Если первая буква в строке «a», то Элизабет дописывает в конец строки «bc», после чего удаляет из строки первые 2 буквы.
- Если первая буква в строке «b», то тогда Элизабет дописывает в конец строки «a», после чего также удаляет из строки первые 2 буквы.
- Если же первая буква в строке «c», то Элизабет дописывает в конец строки «aaa», после чего опять удаляет из строки первые 2 буквы.
Элизабет останавливается после того, как у нее получится строка, состоящая из одной буквы. Например, при
n = 4, для достижения цели ей требуется 6 шагов:
Элизабет обнаружила, что для некоторых
n нужно делать слишком много операций, и не понятно, завершится ли процесс вообще. Поэтому она попросила Вас написать для этого программу.
