Right-angled Triangle#1049

Right-angled Triangle

1 second
128 megabytes
Hard

A triangle is one of the basic geometric shapes: a polygon with three vertices, not lying on a straight line, and three sides, which are its line segments. A triangle with vertices , , and is denoted as .

Triangles can be classified by their internal angles as follows:

prb1049-ua

Your task is very simple. For a given natural number , count how many different right-angled triangles satisfy a + b + c \leq L, where and are the legs and is the hypotenuse. Note that , , and must all be integers.

Input

Multiple test cases. Each test consists of a single integer (12 \leq L \leq 2 \times 10^6).

Output

For each test, output on a separate line the number of different right-angled triangles for which a + b + c \leq L.

Examples

Example 1

Loading
Loading

Note

There are different right-angled triangles with a + b + c \leq 40. Their side lengths are:

  • a = 3, b = 4, c = 5

  • a = 6, b = 8, c = 10

  • a = 5, b = 12, c = 13

  • a = 9, b = 12, c = 15

  • a = 8, b = 15, c = 17