题目描述

孙悟空当上弼马温后原本还是兢兢业业的，但是听说弼马温是个闲职后，心中苦闷，偷来了玉皇大帝的琼浆玉液，借酒消愁。

酒后他就一个人玩起了游戏，御马监共有 n 间马舍，编号为 1 到 n ，因为御马脾气都很大，所以一间马舍只会有一匹御马，且马舍门都是关上的。第一轮，孙悟空从马舍一头走到另一头，把所有马舍门都打开了；第二轮，他又把所有编号是 2 的倍数的马舍门关上了；第三轮，他把所有编号是 3 的倍数的马舍门检查了一遍，如果是开着的，就锁上，否则就打开。在玩了 n 轮后，孙悟空就醉倒了。

孙悟空醉倒后，御马终于可以放飞自我了，请问最多会有多少匹御马出逃？

输入格式

输入一个正整数 n，表示马舍的数量。

输出格式

输出一个整数表示最多会有多少匹御马逃走。

样例输入 1

5

样例输出 1

2

样例输入 2

3

样例输出 2

1

样例输入 3

1000

样例输出 3

31

说明

样例 1 解释

• 第一轮：开 开 开 开 开；
• 第二轮：开 关 开 关 开；
• 第三轮：开 关 关 关 开；
• 第四轮：开 关 关 开 开；
• 第五轮：开 关 关 开 关；

孙悟空醉倒时有两间马舍没有锁，所以最多会有两匹马逃走。

数据范围

对于 100% 的数据，满足 n ≤ 1e18 。