Tý muốn cắt một sợi dây có chiều dài N (mét) thành 3 đoạn dây có chiều dài mỗi đoạn là số nguyên dương (đơn vị mét) sao cho 3 đoạn dây này là 3 cạnh của một tam giác cân có cạnh đáy lớn hơn cạnh bên.

Lưu ý: Tam giác cân là tam giác có hai cạnh bằng nhau, hai cạnh bằng nhau gọi là hai cạnh bên, cạnh còn lại gọi là cạnh đáy.

Yêu cầu: Em hãy giúp Tý tính có bao nhiêu cách cắt đoạn dây này.

Input

Một dòng chứa số nguyên dương N (N ≤ 10¹⁶).

Output

In ra một số nguyên M là số cách cắt sợi dây theo yêu cầu.

Ví dụ

Input

19

Output

2

Giải thích

Có 2 cách cắt sợi dây thành 3 đoạn thỏa mãn đề bài là:

(5; 5; 9) và (6; 6; 7).

Lưu ý

Các cách cắt sợi dây thành 3 đoạn (x; x; y) và các hoán vị của bộ ba số (x; x; y) chỉ được tính là 1 cách cắt. Chẳng hạn, các cách cắt thành các đoạn (5; 5; 9), (5; 9; 5) và (9; 5; 5) đều chỉ được tính là một cách.

Giới hạn

20% số test ứng với N ≤ 10².

30% số test ứng với 10² < N ≤ 10⁶.

30% số test ứng với 10⁶ < N ≤ 10⁹.

20% số test ứng với 10⁹ < N ≤ 10¹⁶.