Source

This problem is adapted from Long Long OJ. All rights reserved.

Description

Given an integer $n$, find all valid pairs $(a,b,c)$ consisting of three integers that satisfy the following conditions:

• $1 \leq a \lt b \lt c\leq n$
• $a^{2}+b^{2}=c^{2}$

Input

An integer $n$.

Output

Output the sum of $c$ over all the valid pairs $(a,b,c)$.

Samples

5

5

20

80

Tips

Sample Explanation 2:

The valid pairs are: $(3,4,5),(6,8,10),(5,12,13),(9,12,15),(8,15,17),(12,16,20).$

As a result, the answer is $5+10+13+15+17+20=80.$

For $100\%$ of the testcases, $1\leq n\leq 10^6$.