题目描述

杨辉三角定义如下。

第一层有两个数 $A_{1,1}$ 和 $A_{1,2}$，满足 $A_{1,1} = A_{1,2} = 1$。

对于每个 $i > 1$，第 $i$ 层包含 $i+1$ 个数，满足 $A_{i,1} = A_{i,i+1} = 1$，且对于 $1 < j \le i$ 有 $A_{i,j} = A_{i-1,j-1} + A_{i-1,j}$。

$$\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}$$

现在给定一个整数 $N$，请你统计前 $N$ 层中偶数的个数。

输入格式

输入文件包含多组测试数据，请处理到文件末尾。

每组数据仅有一行，包含一个整数 $N$（$0 < N \le 10^{50}$）。

输出格式

对于每组数据，输出杨辉三角前 $N$ 层中偶数的个数。

4
8
12

4
16
42

提示

翻译由 DeepSeek V4 Pro 完成