题目描述

$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)$ 的值。

5

3

1000000

318279

123456789101112

39297516488187

数据范围与提示

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

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

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