该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“赛后递交”以递交本题。

题目描述

类似 $222，131313$ 这样的，由 $1$ 个数字字符串重复 $3$ 次形成的整数，称作“三倍数”。但是 $000,010101$ 这样开头是 $0$ 的字符串不算做“三倍数”。

给出一个很大的整数 $M$ ，求小于等于 $M$ 的正整数中，有多少个“三倍数”？

输入格式

$1$ 个正整数 $M$

输出格式

输出小于等于 $M$ 的“三倍数”的个数。

输入输出样例

4000

9

样例 $\tt \#1$说明

满足条件的有$111,222,333,444,555,666,777,888,999$。

222222222333333333111111111

222222222

样例 $\tt \#2$说明

输入输出可能超过 $64$ 位无符号整数类型范围

数据范围

$20\%$ 数据，$M\le10^6$

$50\%$ 数据，$M≤10^{18}$

$100\%$ 数据，$1≤M≤10^{1000}$