G. Fibonacci
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

In mathematics, the Fibonacci numbers, commonly denoted as $$$f_n$$$, is a sequence such that each number is the sum of the two preceding numbers, starting with $$$1$$$ and $$$1$$$. That is, $$$f_1 = 1, f_2 = 1$$$ and $$$f_n = f_{n-2} + f_{n-1}~(n \ge 3)$$$.

Thus, the beginning of the sequence is $$$1, 1, 2, 3, 5, 8, 13, 21,\ldots$$$ .

Given $$$n$$$, please calculate $$$\sum_{i=1}^{n}{\sum_{j=i+1}^{n}{g(f_i,f_j)}}$$$, where $$$g(x,y) = 1$$$ when $$$x \cdot y$$$ is even, otherwise $$$g(x,y) = 0$$$.

Input

The only line contains one integer $$$n~(1\le n\le 10^9)$$$.

Output

Output one number – $$$\sum_{i=1}^{n}{\sum_{j=i+1}^{n}{g(f_i,f_j)}}$$$.

Examples
Input
3
Output
2
Input
10
Output
24
Input
100
Output
2739