[AdditionalFile6849.zip](file://AdditionalFile6849.zip?type=additional_file)

#6849. zydy 与积性函数

标签: 传统 | 时间限制: 2000 ms | 内存限制: 128 MiB |

题目描述

$zydy$ 发现了一个有趣的积性函数 $f(x)$，其满足：

1. $f(1)=1$

2. $f(p^{c})=\begin{cases}2&p\equiv1\pmod{4}\\0&\text{else}\end{cases}$

令 $S(n)=\sum\limits_{i=1}^{n}f(i)$，请你帮 $zydy$ 求出 $S(n)$ 的值。

输入格式

一行一个正整数 $n$。

输出格式

一行一个整数表示 $S(n)$ 的值。

样例 1

输入

5

输出

3

$S(5)=f(1)+f(2)+f(3)+f(4)+f(5)=1+0+0+0+2=3$。

样例 2

输入

1000000

输出

318279

样例 3

输入

123456789101112

输出

39297516488187

数据范围与提示

对于 $20\%$ 的数据，$n\le10^{8}$，

对于 $50\%$ 的数据，$n\le10^{12}$，

对于 $100\%$ 的数据，$n\le10^{15}$。