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