Pythagorean Triples

A Pythagorean triple consists of three positive integers \(a\), \(b\), and \(c\) such that \(a^2 + b^2 = c^2\) and \(1 \le a \le b \le c\). Given an integer \(n\), your task is to count how many triples \((a, b, c)\) exist with \(c \le n\).

For example, when \(n = 5\), the only valid triple is \((3, 4, 5)\), hence the answer is 1.

inputFormat

The input consists of a single integer \(n\) (\(n \ge 1\)), representing the upper bound for \(c\).

outputFormat

Output a single integer representing the number of Pythagorean triples with \(c \le n\).

sample

5

1