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 gịá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.

Dữ liệu

• Một số nguyên dương \(N\) (\(N< 10^{16}\))

Kết quả

• Ghi ra số \(M\) là số cách cắt sợi dây theo yêu cầu.

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 đề là: (\(5m; 5m; 9m\)) và (\(6m; 6m; 7m\)).

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

Giới hạn

• Có 20% test ứng với \(N \le 10^2\);
• Có 30% test ứng với \(10^2 < N \le 10^6\);
• Có 30% test ứng với \(10^6 < N \le 10^9\);
• Có 20% test ứng với \(10^9 < N \le 10^{16}\).

Nguồn: THTB - Cấp TP 2021.