题目描述

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

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

输入格式

在文件 gcd.in 中读入。

输入一个正整数 $n$。

输出格式

在文件 gcd.out 中输出。

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

样例

样例输入 #1

7

样例输出 #1

4

样例 1 解释

满足条件的无序数对有：

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

样例输入 #2

114514

样例输出 #2

198982

样例输入 #3

1919810

样例输出 #3

3349879

大样例

数据范围

• 对于前 $30\%$ 的数据，$n \le 1000$；
• 对于前 $60\%$ 的数据，$n \le 10^5$；
• 对于所有数据，$1 \le n \le 10^7$。