Heap of boxes P44911

Statement

Consider a heap with $n$ boxes at the bottom. The next row has $n-1$ boxes, the following row $n-2$ boxes, and so on. The boxes at the bottom row can store any integer numbers, but every other box must contain the sum of the two boxes underneath. The figure shows an example for $n = 4$ :

(8,7)

(2,2)(10,2) (2,3)(10,3) (3,4)(9,4) (4,5)(8,5) (5,6)(7,6)

(3,3)(3,4) (5,3)(5,4) (5,5)(5,6) (7,3)(7,4) (7,5)(7,6) (9,3)(9,4) (2,2)(2,3) (4,2)(4,3) (4,4)(4,5) (6,2)(6,3) (6,4)(6,5) (8,2)(8,3) (8,4)(8,5) (10,2)(10,3)

(3,2.5)23 (5,2.5)19 (7,2.5)6 (9,2.5)3 (4,3.5)42 (6,3.5)25 (8,3.5)9 (5,4.5)67 (7,4.5)34 (6,5.5)101

Given $n$ , you must fill the heap of boxes with integer numbers, according to the rules above. Your goal is to maximize the total quantity of odd numbers. For instance, the figure proves that 7 odd numbers are possible for $n = 4$ . In fact, 7 is the maximum for $n = 4$ .

Input

Input consists of several cases, each one with a natural number $n$ between 1 and 28.

Output

For every $n$ , print the maximum number of odd numbers that a heap with $n$ boxes at the bottom can contain according to the given rules.

Public test cases

Input

1
4
25

Output

1
7
217

Information

Author: Salvador Roura
Language: English
Official solutions: C++
User solutions: C++