题目描述

小 M 今天学习了乘方运算。具体地，$x^n$ 表示把 $n$ 个 $x$ 相乘的结果，例如 $2^4=2\times 2\times 2\times 2=16$。

为了巩固他的学习成果，老师给他布置了一道题：

给出正整数 $n$，计算有多少有序正整数对 $(x,y)$ 使得 $2^x+y^2\le n$。

你可以帮他解决这个新问题吗？

输入格式

输入有一行一个正整数 $n$，含义见题目描述。

输出格式

输出一行一个非负整数，表示符合要求的 $(x,y)$ 个数。

12

7

提示

【样例 1 解释】

小 M 想要知道 $2^x+y^2\le 12$ 有多少正整数解。符合题意的 $(x,y)$ 有：

• $(1,1),(1,2),(1,3)$
• $(2,1),(2,2)$
• $(3,1),(3,2)$

【数据范围】

• 对于 $30\%$ 的数据，保证 $1\le n\le 100$。
• 对于 $70\%$ 的数据，保证 $1\le n\le 10^9$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 10^{11}$。