402845: GYM100917 L Liesbeth and the String

Little Liesbeth likes to play with strings. Initially she got a string of length n, consisting of letters 'a' only.

Then Liesbeth performs next operations with the string:

• If the first letter of the string is 'a', then she adds to the end of the string "bc", and after that removes first two letters of the string.
• If the first letter of the string is 'b', then she adds to the end of the string 'a', and after that removes first two letters of the string.
• If the first letter of the string is 'c', then she adds to the end of the string 'aaa" and after that removes first two letters of the string.

Liesbeth stops when she has the string of length 1. For example, if n = 4, she needs 6 operations :

Liesbeth found that for some n number of operations is too big, and its hard to understand if the process is finite. So she asked You to write the program to help her.

First line of the input contains one integer n (2 ≤ n ≤ 10⁶) — length of the initial string.

Print one integer — number of operations needed to obtain string of length 1. If process is infinite, print  - 1 instead.

4

6

3

24