题目描述

Yang Hui’s Triangle is defined as follows.

In the first layer, there are two numbers $A_{1,1}$ and $A_{1,2}$ satisfying $A_{1,1} = A_{1,2} = 1$.

Then for each $i > 1$, the $i$-th layer contains $i+1$ numbers satisfying $A_{i,1} = A_{i,i+1} = 1$ and $A_{i,j} = A_{i-1,j-1} + A_{i-1,j}$ for $1 < j \le i$.

$$\begin{matrix} 1 & 1 \\ 1 & 2 & 1 \\ 1 & 3 & 3 & 1 \\ 1 & 4 & 6 & 4 & 1 \\ 1 & 5 & 10 & 10 & 5 & 1 \\ 1 & 6 & 15 & 20 & 15 & 6 & 1 \\ 1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 \\ 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 \end{matrix}$$

Now, given an integer $N$, you are asked to count the number of even integers in the first $N$ layers.

输入格式

The input file contains multiple cases, please handle it to the end of file.

For each case, there is only one line containing an integer $N$ ($0 < N \le 10^{50}$).

输出格式

For each case, output the number of the even integers in the first $N$ layers of Yang Hui’s Triangle.

4
8
12

4
16
42