题目描述
含有 `49` 的数字是幸运数字，比如 $1498$ 和 $49$ 就是幸运数字，但是 $419$ 和 $94$ 就不是，这两个数字中虽然含有 `4` 和 `9`，但没含 `49`。求 $1 \sim N$ 中有多少个幸运数字？
输入
一行一个正整数 $N$。
输出
共一行，为 $1\sim N$ 中的幸运数的个数。
样例输入输出
提示
对于 $20\%$ 的数据保证数据 $N \leq 1000$；
除上述 $20\%$ 的数据外，另有 $30\%$ 的数据保证 $N = 10^k-1(0 < k \leq 15)$；
对于 $100\%$ 的数据保证 $N < 10^{20}$ ，答案保证不超过 $2^{63}-1$ 范围。