题目描述

上次的密码十分轻易被破解了，导致战略情报被敌方获知。于是ことり决定重新设置一个更强的密码。新密码也需要测试，找不到おりがみ的ことり将目光投向了你……

密码形同下面这个问题:

对于给定的 $n$ 求有多少有序数对 $(a,b,c)$ 满足 $1\le a,b,c\leq n (a,b,c\in N^*)$ 且 $a,b,c$ 构成一个等比数列。

即 $b^2\!=\!ac$。

输入格式

输入共一行一个数，表示 $n$。

输出格式

输出共一行一个数，表示方案数。

10

18

样例说明 1

这 $18$ 个序数对为：

1 1 1
1 2 4
1 3 9
2 2 2
2 4 8
3 3 3
4 2 1
4 4 4
4 6 9
5 5 5
6 6 6
7 7 7
8 4 2
8 8 8
9 3 1
9 6 4
9 9 9
10 10 10

87

249

数据范围

$\texttt{Subtask 1(5 pts): }1 \leq n \leq 100$。
$\texttt{Subtask 2(10 pts): }1 \leq n \leq 2000$。
$\texttt{Subtask 3(15 pts): }1 \leq n \leq 10^5$。
$\texttt{Subtask 4(30 pts): }1 \leq n \leq 10^7$。
$\texttt{Subtask 5(25 pts): }1 \leq n \leq 10^{13}$。
$\texttt{Subtask 6(15 pts): }1 \leq n \leq 10^{15}$。

选手 AK 后可以思考一下当 $n=10^{17}$ 时怎么做。