#2334. 勾股三元组

勾股三元组

题目描述

我们规定一个仅包含整数的三元组(a,b,c)\red{(a,b,c)}为"勾股三元组"仅当1<=a<=b<=c\red{1<=a<=b<=c}a2+b2=c2\red{a^2+b^2=c^2,}比如(3,4,5)\red{(3,4,5)} 就是"勾股三元组"。

Vasya\red{Vasya}最近刚刚学习了勾股定理,然后就把判断"勾股三元组"的方法记错了,他记成了a2b=c\red{a^2-b=c,}但 惊奇的是,对于某些"勾股三元组",这个式子是成立的(比如刚刚提到的(3,4,5)\red{(3,4,5))}。现在给定n\red{n,}求出 有多少"勾股三元组"(a,b,c)\red{(a,b,c)}满足a,b,c<=n\red{a,b,c<=n}a2b=c\red{a^2-b=c}

输入格式

一行一个整数n\red{n,}表示约束。

输出格式

一行一个整数,表示有多少"勾股三元组"(a,b,c)\red{(a,b,c)}满足a,b,c<=n\red{a,b,c<=n}a2b=c\red{a^2-b=c}

样例

输入样例

3

输出样例

0

提示

对于50%\red{50\%}的数据,1<=n<=106\red{1<=n<=10^6}

对于100%\red{100\%}的数据,1<=n<=109\red{1<=n<=10^9}