题目描述

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

输入格式

单个正整数：表示 n。

输出格式

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

数据范围

对于 30% 的数据：1≤n≤10⁶；

对于 60% 的数据：1≤n≤10⁹；

对于 100% 的数据：1≤n≤10¹⁸。

样例数据

输入:

20

输出:

19

输入:

200

输出:

188

说明:

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