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。

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

【样例 1 解释】

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

数据范围

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

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

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

CSP-J模拟赛