题目描述

D是一名特工，他收到的密信都是一串二进制数字。

他发现了一个规律：如果一串二进制数中 1 的个数是素数，那么这串数字就是"有效密文"。

现在小D收到了一串长度为 60 的二进制数，他想知道在 [0, n] 范围内，有多少个"有效密文"。

输入格式

一行一个整数 n。

输出格式

一行一个整数，表示有效密文的数量。

样例

10

5

数据范围与提示

请在此处填写数据范围与提示。