Luke 是一名充满好奇心的数学探险家。他最近迷上了一种神秘的数字游戏，游戏规则很简单：在一片数字大陆上，Luke 需要找到特定的数字对。

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

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

现在，Luke 需要你的帮助，来找出在给定的数字范围内有多少对符合要求的数字对。

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

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

样例 1 解释

\gcd(2,3) = 1 = 2 \oplus 3，所以 n = 3 时答案为 1。

数据范围

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

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

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