Practice Number theory and Mathematics with the exercise "Primitive Pythagorean Triples"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Number theory
Mathematics

Statement

Goal

In this problem, we are given an input integer N, and your goal is to find the number of all primitive Pythagorean triples up to and including N.

A Pythagorean triple is a triple (a, b, c), where a, b and c are positive integers such that a² + b² = c². We want to find the number of all of these triples, such as 0 < a, b, c ≤ N, with a < b < c and exclude any multiples of other triples. For example, we do not want to count the triple (6, 8, 10), since it is a multiple of the triple (3, 4, 5).

Input

Line 1: An integer N.

Output

Line 1: Number of all primitive Pythagorean triples up to and including N.

Constraints

0 < N ≤ 10⁶

Example

Input

Output

Solve it

A higher resolution is required to access the IDE