Russell Westbrook has farmed enough triple doubles in his career and is now pursuing a passion for triple triplets. Let the Triple value of an array $A$ be the number of distinct triplets $1\le i<j<k\le |A|$ such that $A_i+A_j=A_k$. For example, the Triple value of the array $[1,2,10,3]$ is $1$. The only triplet that satisfies this condition is $(1,2,4)$, as $A_1+A_2=A_4$. Please tell Russell the maximum Triple value of all possible arrays with positive integer values that add up to $N$.

Constraints

$1\le N\le {10}^6$

Subtask 1 [20%]

$1\le N\le 15$

Subtask 2 [80%]

No additional constraints.

Input Specification

The first and only line contains the integer $N$.

Output Specification

Output the maximum Triple value of all possible arrays with positive integer values that add up to $N$.

Sample Input

5

Sample Output

3