题解

题目描述

如果三个正整数 $a,b,c$ 满足 $a\times b,\ b\times c,\ a\times c$ 都是完全平方数，那么称 $(a,b,c)$ 为一个平方三元组。
现在给出正整数 $n$，请你求出满足

的平方三元组 $(a,b,c)$ 的数量。

题目内容

如果三个正整数 $a, b, c$ 满足 $a×b,b×c,a×c$ 都是完全平方数，那么称 $(a,b,c)$ 为一个平方三元组。

现在给出正整数 $n$ ，请你求出满足 $1≦ a< b<c≦n$ 的平方三元组 $(a,b,c)$ 的数量。

输入描述

输入一个正整数 $n$ 。

$1≤n≤2×10^5$

输出描述

输出一个整数，表示答案。

样例1

输入

9

输出

1

说明

满足条件的三元组只有 $[1,4,9]$ 。

样例2

输入

16

输出

4

说明

满足条件有以下三元组：

$[1,4,9]$

$[1,4,16]$

$[1,9,16]$

$[4,9,16]$