题目描述

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

输入

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

输出

输出共一行，一个正整数表示答案。

输入样例

3

输出样例

1

提示

【样例解释】 只有$(2,3)$满足要求。 【数据规模】 对于30%的数据，$n≤1000$。 对于60%的数据，$n≤10^5$。 对于100%的数据，$n≤10^7$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。