Ba số nguyên dương ~a,b,c~ là các cạnh của một tam giác vuông nếu thỏa mãn ~a \le b < c~ và ~a^2+b^2=c^2~.

Yêu cầu

Cho số nguyên dương ~N~, hãy đếm số bộ ba số nguyên dương ~a,b,c~ thỏa mãn ~1 \le a \le b < c \le N~ và tạo thành một tam giác vuông.

Input

Một dòng chứa số nguyên dương ~N~ ~(1 < N \le 10^4)~.

Output

In ra một số nguyên là số lượng tam giác vuông đếm được.

Subtask

• Subtask 1: ~N~ nhỏ, có thể duyệt ba vòng lặp.
• Subtask 2: ~N \le 10^4~.

Ví dụ 1

10

2

Ví dụ 2

15

4