Problem Description

总教头最近迷上了一种神秘的数字游戏，游戏规则很简单：在一片数字大陆上，总教头 需要找到特定的数字对。每次，他都要选择两个数字 $a$ 和 $b$，并且要求它们满足一些奇特的关系。

在这片数字大陆上，有一个强大的神秘力量，它就是“最大公约数”（gcd），以及一个神秘的运算符“异或”（xor）。Luke 的任务是找到一对 $a$ 和 $b$ 满足 $\operatorname{gcd}(a, b) = a \operatorname{xor} b$。

然而，这并不是那么简单！总教头 发现这对数字必须位于 $[1, n]$ 之间，且他只能找出无序的数字对，也就是说 $(a, b)$ 和 $(b, a)$ 是相同的。

现在，总教头 需要你的帮助，来找出在给定的数字范围内有多少对符合要求的数字对。快来帮助 总教头 一起解开这个谜题吧！

Input Format

输入共一行，一个整数 $n$。

Output Format

输出一行一个整数，即答案。

3

1

588

887

1234567

2153842

Hint

【样例 1 解释】

$\gcd(2,3)=2 \oplus 3=1$

【数据范围】

对于$30\%$的数据，$n \le 10^3$

对于$60\%$的数据，$n \le 10^5$

对于$100\%$的数据，$n \le 10^7$