题目描述

给定 $n$，请你求出

$$\sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=1}^{i}[(i,j),(i,k)]$$

答案对 $2^{32}$ 取模。

说明：按竞赛中常见记号，$(a,b)$ 往往表示 $\gcd(a,b)$，$[a,b]$ 往往表示 $\mathrm{lcm}(a,b)$

输入格式

一行一个数 $n(n\le 9233333333)$ 描述询问。

输出格式

一行一个数表示答案。

Samples

23

18690