题目描述

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

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

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

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

输入格式

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

输出格式

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

3

1

588

887

1234567

2153842

数据范围

【样例 1 解释】

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

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

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

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