在数学中，斐波那契数列通常记作 $f_n$，是一个满足每个数都是前两个数之和的数列，起始项为 1 和 1。即 $f_1 = 1, f_2 = 1$ 且 $f_n = f_{n-2} + f_{n-1}$ ($n \ge 3$)。
因此，该数列的开头为 $1, 1, 2, 3, 5, 8, 13, 21, \dots$。
给定 $n$，请计算 $\sum_{i=1}^{n} \sum_{j=i+1}^{n} g(f_i, f_j)$，其中当 $x \cdot y$ 为偶数时 $g(x, y) = 1$，否则 $g(x, y) = 0$。
输入格式
仅一行，包含一个整数 $n$ ($1 \le n \le 10^9$)。
输出格式
输出一个数字，即 $\sum_{i=1}^{n} \sum_{j=i+1}^{n} g(f_i, f_j)$ 的值。
样例
样例输入 1
3
样例输出 1
2
样例输入 2
10
样例输出 2
24
样例输入 3
100
样例输出 3
2739