Số chính phương

Bình là một cậu bé rất đam mê toán học, đặc biệt là phần số học. Giải các bài toán về số nguyên tố, số chính phương, chia hết, ... là sở trường của Bình. Nhân dịp Kỳ thi Duyên hải năm nay được tổ chức lần đầu tiên theo hình thức thi online, Bình gửi đến các bạn một bài toán liên quan đến số chính phương.

Với số tự nhiên $n$ cho trước, Bình yêu cầu bạn đếm số bộ ba số nguyên $(a,b,c)$ với $1\le a<b<c\le n$ sao cho tất cả các tích $a\times b$, $a\times c$ và $b\times c$ đều là các số chính phương.

Yêu cầu: Hãy lập trình giúp Bình tìm số lượng bộ ba số $(a,b,c)$ thỏa mãn.

Dữ liệu vào

Duy nhất số nguyên dương $n$ ($n\le 5·{10}^6$).

Dữ liệu ra

In ra số lượng bộ ba số $(a,b,c)$ tìm được.

Ràng buộc

• $1\le n\le 5·{10}^6$.

Subtasks

• Subtask 1 ($24\%$ số điểm): $1\le n\le 100$.
• Subtask 2 ($20\%$ số điểm): $100<n\le 5000$.
• Subtask 3 ($28\%$ số điểm): $5000<n\le {10}^5$.
• Subtask 4 ($28\%$ số điểm): ${10}^5<n\le 5·{10}^6$.

Ví dụ