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.

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.

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.

Scoring

• Subtask ~1~ (~20\%~ số điểm): ~N\le 10^2~.
• Subtask ~2~ (~30\%~ số điểm): ~10^2 \le N\le 10^6~.
• Subtask ~3~ (~30\%~ số điểm): ~10^6 \le N \le 10^9~
• Subtask ~4~ (~20\%~ số điểm): ~10^9 \le N \le 10^{16}~

Ví dụ

Input

19

Output

2

Giải thích ví dụ

• 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)~.