L. Liesbeth and the String
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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

Output

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

Examples
Input
4
Output
6
Input
3
Output
24