小鬼位于魔法森林中,那里生长着 xorangles(什么?)
n 阶异或角是一种非简并三角形,其边长为不超过 n 的整数,且长度的异或和等于 0。 Imp 必须计算 n 阶不同 xorangle 的数量才能离开森林。
形式上,对于给定的整数 n,您必须找到这样的三元组 (a, b, c) 的数量,即:
- 1 ≤ a ≤ b ≤ c ≤ n;
- $$a \oplus b \oplus c = 0$$,其中 $$x \oplus y$$ 表示整数 x 和 y 的按位异或。
- (a, b, c) 形成一个非退化(面积严格为正)三角形。
输入
唯一一行包含单个整数 n (1 ≤ n ≤ 2500)。
输出
打印 n 阶 xorangle 的数量。
示例
输入 #1
6
输出 #1
1
输入 #2
10
输出 #2
2
注意
第一个样本中唯一的异形是 (3, 5, 6)。