The Garland

The New-year tree decorated by the garland of endless length which consists of the consistently united bulbs. When a garland is turn on only the first bulb lights up in the way from a switch and its burns one second. Then a garland begins to blink by such rule. In every second for every bulb is checking up a condition: if only one adjacent bulb is burning, this bulb will burn on a next second; else – it will not burn. The first bulb has only one nearby.

You have to write the program that by the number of second will find the quantity of bulbs of garland that will burn during this second.

Input

One integer n (1 ≤ n ≤ 10^9) - the number of the second.

Output

Print one integer - the number of bulbs that will be burning at the second number n.

Examples