描述

给定一个如下形式的方程:

x^2+y^2=z^4(gcd(x,y)=1)

求此方程在z\in [1,Max]的所有正整数解

输入格式

一个整数Max

输出格式

一个整数表示解的个数

样例输入

39

样例输出

12

数据范围与约定

对于40%的数据Max\in [1,100]

对于70%的数据Max\in [1,1000000]

对于100%的数据Max\in [1,100000000]

题目来源

原创By XTC