L. Игра со строкой
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленькая Элизабет любит играть со строками. У нее есть строка длины n, полностью состоящая из букв «a». Она делает со строкой следующие действия:

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

В единственной строке дано одно целое число n (2 ≤ n ≤ 106).

Выходные данные

Выведите одно число — количество требуемых шагов. Если процесс будет продолжаться бесконечно — выведите  - 1.

Примеры
Входные данные
4
Выходные данные
6
Входные данные
3
Выходные данные
24