题目描述

若一个整数在十进制下不含 $13$ 作为子串，则称它为平安数，例如 $123$ 是平安数，但 $2132$ 不是平安数。给定一个 $n$，请计算从 $1$ 到 $n$ 有多少个平安数。

输入格式

单个整数：表示 $n$。

输出格式

单个整数：表示 $1$ 到 $n$ 之间有多少整数的十进制表示不含 $13$ 子串。

20

19

200

188

样例解释 2

13、113以及130到139都不是平安数

数据范围

• 对于 $30\%$ 的数据：$1\leq n\leq 10^6$；
• 对于 $60\%$ 的数据：$1\leq n\leq 10^9$；
• 对于 $100\%$ 的数据：$1\leq n\leq 2^{63}-1$。