题目描述

lxc 是一个擅长吃的仙人，既然是仙人嘛，自然对吃的东西有一定的要求，比方说吃牛肉。

首先，lxc 是非牦牛肉不吃的，其次，lxc 每次只在 $3$ 头牦牛中选 $1$ 头来吃，并且这三头牦牛的长度还要满足以下条件：不妨设这三头牦牛的长度为 $a, b, c\ (a < b < c)$，则 $a^2+b^2=c^2$。

lxc 养了很多头牦牛，每头牦牛的长度都不大于 $N$，每种长度的牦牛都有。作为 lxc 弟子的你想知道，一共有多少种不同的方案用来安排给 lxc 准备牦牛肉。即给定一个正整数 $N$，找出符合 $a^2+b^2=c^2$ 的三元组 $(a,b,c)$ 的总数，其中 $a<b<c \le N$。

输入格式

仅有一行包含一个正整数 $N$

输出格式

仅有一行包含一个整数，表示安排食谱的方案总数

10

2

样例说明

只有两种方案：$a=3,b=4,c=5$ 或 $a=6,b=8,c=10$。

数据范围

$30\%$ 的数据满足 $N\leq300$

$60\%$ 的数据满足 $N\leq20000$

$100\%$ 的数据满足 $N\leq1000000$