题目背景

如果 $1001=2,1867=3,1902=2$，那么 $2108=\_\_$？

答案：$3$。

题目描述

定义一个 $\N\to\N$ 的函数 $f(x)$，其函数值是十进制下每个数字封闭环的个数之和，$0\sim9$ 的十个数字的封闭环的个数分别是：

::cute-table{tuack} |$n$|$0$|$1$|$2$|$3$|$4$|$5$|$6$|$7$|$8$|$9$| |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$f(n)$|$1$|$0$|$0$|$0$|$1$|$0$|$1$|$0$|$2$|$1$|

上面的表格可以看作是函数的初始值，递推式就是

$$f(10n+m)=f(n)+f(m),n\in\N^*,m\in\{0,1,2,3,4,5,6,7,8,9\},$$

但是这个 $m$ 的限制较多，所以问题是：对于给定的正整数 $n$，求出有多少个不超过 $n$ 的自然数 $m$，满足 $f(10n+m)=f(n)+f(m)$。

输入格式

一行，一个正整数 $n$。

输出格式

一行，一个整数，表示 $0\le m\le n$ 中满足 $f(10n+m)=f(n)+f(m)$ 的 $m$ 的个数。

6

7

25

16

33554432

4701180

1145141919810

7537415110

提示

样例 $1$ 解释

由递推式可知所有小于等于 $6$ 的非负整数 $m$ 都满足 $f(10\times 6+m)=f(6)+f(m)$。

样例 $2$ 解释

根据递推式，满足 $0\le m\le 9$ 的整数 $m$ 符合题目要求，另外还有 $20,21,22,23,24,25$ 六个数字，原因如下：

• $f(10\times 25+20)=f(270)=1=f(25)+f(20)$；
• $f(10\times 25+21)=f(271)=0=f(25)+f(21)$；
• $f(10\times 25+22)=f(272)=0=f(25)+f(22)$；
• $f(10\times 25+23)=f(273)=0=f(25)+f(23)$；
• $f(10\times 25+24)=f(274)=1=f(25)+f(24)$；
• $f(10\times 25+25)=f(275)=0=f(25)+f(25)$。

数据范围

对于所有测试数据，保证：$1\le n\le 10^{17}$。

::cute-table{tuack} |测试点编号|$n\le$| |:-:|:-:| |$1\sim 10$|$10^6$| |$11\sim 30$|$5\times 10^7$| |$31\sim 50$|$10^{17}$|