4388: C. gcd (gcd.c/cpp/pas)
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
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 一起解开这个谜题吧！
输入
### Input
输入共一行，一个整数 $n$。
输出
### Output
输出一行一个整数，即答案
样例输入 复制
3样例输出 复制
1提示
### Examples
#### 【样例 1 输入】
```input
3
```
#### 【样例 1 输出】
```output
1
```
#### 【样例 1 解释】
$\gcd(2,3)=2 \oplus 3=1$
#### 【样例 2 输入】
```input
588
```
#### 【样例 2 输出】
```output
887
```
#### 【样例 3 输入】
```input
1234567
```
#### 【样例 3 输出】
```output
2153842
```
### Notes
对于$30\%$的数据，$n \le 10^3$
对于$60\%$的数据，$n \le 10^5$
对于$100\%$的数据，$n \le 10^7$