杨辉三角定义如下： 第一层有两个数 $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}$。
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
现在，给定一个整数 $N$，请你计算前 $N$ 层中偶数的个数。
输入格式
输入文件包含多组测试数据，请处理到文件末尾。 对于每组数据，仅包含一行，为一个整数 $N$ ($0 < N \le 10^{50}$)。
输出格式
对于每组数据，输出前 $N$ 层杨辉三角中偶数的个数。
样例
样例输入 1
4 8 12
样例输出 1
4 16 42