该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

gcd & xor

题目描述

给定一个正整数 $n$，在 $[1, n]$ 的范围内，求出有多少个无序数对 $(a, b)$ 满足

其中 $\gcd(a, b)$ 表示 $a$ 和 $b$ 的最大公约数，$\oplus$ 表示按位异或运算。

输入格式

输入一个正整数 $n$。

输出格式

输出一个整数，表示满足条件的无序数对的数量。

样例 #1

样例输入 #1

7

样例输出 #1

4

样例解释 #1

满足条件的无序数对有：

• $(2, 3)$
• $(4, 5)$
• $(4, 6)$
• $(6, 7)$

样例 #2

样例输入 #2

114514

样例输出 #2

198982

样例 #3

样例输入 #3

1919810

样例输出 #3

3349879

数据规模与约定

对于前 $30\%$ 的数据，$n \leq 1000$。

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

对于所有数据，$1 \le n \leq 10^7$。