异或

【题目描述】

给定一个正整数$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$。