题目描述

在一个遥远的星系中，有一个以贸易为主的文明——赛伦星人。他们相信某些特殊的数字能够带来好运，这些数字被称为“幸运数字”。根据赛伦星人的传统，一个“幸运数字”需要满足以下两个条件：

1. ​和为奇数​：数字的所有位数之和必须是奇数。
2. ​递归幸运​：如果 数字的所有位数之和小于它本身，那么这个 位数之和 也必须是一个“幸运数字”，这代表着好运的传递和延续。

小 $y$ 想知道 $1$ 到 $n$ 中有多少个“幸运数字”，你能帮帮她吗？

输入格式

输入第一行一个整数 $n$ 。

$n≤10^5$。

输出格式

输出一个整数，表示范围内的 "幸运数字" 的个数。

15

8

100

31

提示

数据 $1$ 的幸运数字分别为：

1 3 5 7 9 10 12 14