题目描述

定义一个二元组 $(i,j)$ 是好的，当且仅当 $i$ 和 $j$ 均为整数且其二进制和三进制表示在相加时都不进位。

给定 $n$，求满足 $1\le i,j\le n$ 的二元组 $(i,j)$ 中好二元组的数量。

输入格式

一行共一个整数 $n$。

输出格式

一行共一个数 $m$，表示满足要求的好二元组数量。

样例输入 #1

4

样例输出 #1

4

样例解释 #1

满足条件的二元组为 $(1,4)$，$(3,4)$，$(4,1)$ 和 $(4,3)$。下举两例作为参考，其余同理可得。

对于 $(1,2)$，

$$1+2=3$$ $$1=(1)_2,2=(10)_2,3=(11)_2$$ $$1=(1)_3,2=(2)_3,3=(10)_3$$

易知其在二进制下符合要求，三进制下不符合要求。故 $(1,2)$ 不是好的二元组。

对于 $(3,4)$，

$$3+4=7$$ $$3=(11)_2,4=(100)_2,7=(111)_2$$ $$3=(10)_3,4=(11)_3,7=(21)_3$$

易知其在二进制和三进制下均符合要求。故 $(3,4)$ 是好的二元组。

样例输入 #2

10

样例输出 #2

16

数据规模与约定

本题目采用 $\text{subtask}$ 测试。

对于 $100\%$ 的数据，$1\le n\le 5000$。

具体数据范围如下：

$\text{subtask 1(10pts)}$：$1\le n\le 10$；

$\text{subtask 2(20pts)}$：$1\le n\le 100$；

$\text{subtask 3(20pts)}$：$1\le n\le 1000$​；

$\text{subtask 4(50pts)}$：无特殊限制。