Cho số nguyên dương ~n~.

Hãy đếm số bộ ba số nguyên dương ~\left(a,b,c\right)~ thỏa mãn đồng thời:

• ~1 \le a < b < c \le n~
• ~ab~, ~ac~, ~bc~ đều là số chính phương

Yêu cầu

Tính số lượng bộ ba thỏa mãn điều kiện trên.

Dữ liệu

Gồm một dòng duy nhất chứa số nguyên dương ~n~.

Kết quả

In ra một số nguyên duy nhất là số lượng bộ ba ~\left(a,b,c\right)~ thỏa mãn.

Ví dụ

Ví dụ 1

Input

941

Output

7351

Ví dụ 2

Input

7359

Output

197497

Giải thích

Ví dụ 1

Có đúng ~7351~ bộ ba ~\left(a,b,c\right)~ thỏa mãn:

• ~1 \le a < b < c \le 941~
• ~ab~, ~ac~, ~bc~ đều là số chính phương

Ví dụ 2

Có đúng ~197497~ bộ ba ~\left(a,b,c\right)~ thỏa mãn:

• ~1 \le a < b < c \le 7359~
• ~ab~, ~ac~, ~bc~ đều là số chính phương

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 5 \times 10^6~

Chấm điểm

• Có ~30%~ số test, tương ứng ~30%~ số điểm, có ~n \le 10^2~
• Có ~40%~ số test, tương ứng ~40%~ số điểm, có ~100 < n \le 10^3~
• Có ~30%~ số test, tương ứng ~30%~ số điểm, có ~1000 < n \le 10^4~