单点时限: 2.0 sec
内存限制: 256 MB
中国自古以九五为至尊，cdm 受此启发想要出一道相关的题目。cdm 觉得两个数字一起用题目可能题目就会比较难了，因而 cdm 选取了九为主题出题。
定义至尊数为任意相邻两位的和均为 9 的合法正整数，比如 $18\quad 363$ 为至尊数，而 $233\quad 362$ 不是至尊数。合法正整数不具有前导零。$1$ 至 $9$ 中的数不含有相邻位，此处约定这些数中只有 $9$ 为至尊数。cdm 想要知道长度不超过 $n$ 的正整数中有多少至尊数。
有多组输入，每组输入有一行正整数 $n$。
保证对于 $40\%$ 的数据，$n \leq 10^8$。
保证对于 $100\%$ 的数据，$n \leq 10^{10000}$。
对于每组输入输出一行结果。
1 3 7 9999999999999997
1 19 55 89999999999999965