公约数

公约数

暂无测试数据。

Background

Description

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

Format

Input

输入共一行, 一个正整数n。

Output

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

Sample

Input

3

Output

1

Explanation

只有(2,3)满足要求。

Limitation

对于30%的数据满足n<=1000
对于60%的数据满足n<=10^5
对于100%的数据满足n<=10^7
1s, 256000KiB for each test case.

Hint

Source

CDQZ TEST

信息

难度
10
分类
数论 点击显示
标签
递交数
2
已通过
0
通过率
0%
上传者