题目背景

本题 idea from：Projecteuler P386.

图源：zhihu.

题目描述

反链是序理论中的一个极其优美的结构。

---

给定正整数 $n$，记 $S(n)$ 为 $n$ 的约数构成的集合。

若 $S(n)$ 的子集 $A$ 只包含一个元素，或者 $A$ 中任意一个元素均不能整除其它元素，则称 $A$ 为 $S(n)$ 的反链。

例如：$S(30) = \{1, 2, 3, 5, 6, 10, 15, 30\}$。

• $\{2, 5, 6\}$ 不是 $S(30)$ 的反链。

• $\{2, 3, 5\}$ 是 $S(30)$ 的反链。

hhoppitree 喜欢长的反链，记 $f(n)$ 表示 $S(n)$ 的最长反链长度，她需要你帮忙求出 $ans=\sum\limits_{k=1}^n f(k)$。

如果做不出来，她就会喵的一声扑向你

输入格式

一行一个正整数表示 $n$。

输出格式

一行一个正整数表示 $ans$。

可以证明答案一定在 long long 范围内。

10

12

20

27

2347

6126

9234799

43445933

99234799

524524311

1000000000

5844921982

23477145069

154961952468

提示

样例 $1$：除了 $f(6)=f(10)=2$，其余 $f(k)=1(1\le k\le 10)$。

样例 $2$：除了 $f(6)=f(10)=f(12)=f(14)=f(15)=f(18)=f(20)=2$，其余 $f(k)=1(1\le k\le 20)$。

---

本题采用捆绑测试

对于所有测试数据，保证 $1\le n\le 123477145069\approx 1.2\times 10^{11}$。

可以证明答案一定在 long long 范围内。

Subtask	$n \le$	Score
$1$	$10$	$5$
$2$	$2500$
$3$	$10^6$	$10$
$4$	$10^7$
$5$	$10^8$
$6$	$10^9$	$20$
$7$	$23477145069$
$8$	$123477145069$