题目描述

小Z最近在数学课上学习了一种有趣的数字——倍增数。倍增数的定义如下：

1. 它是一个正整数，没有前导零。
2. 它的位数 $d$ 是偶数（即 $d = 2k$，其中 $k \geq 1$）。
3. 将数字分成前后两半，每半部分 $k$ 位。
4. 后半部分的每一位数字恰好是前半部分对应位置数字乘以 $2$ 后取个位数（即模 $10$ 的结果）。

例如：

• $12$ 是倍增数：前半部分 $1$，后半部分 $2$，且 $1 \times 2 = 2$。
• $50$ 是倍增数：前半部分 $5$，后半部分 $0$，且 $5 \times 2 = 10 \rightarrow 0$（取个位）。

现在给定一个正整数 $n$，请帮助小Z统计在区间 $[1, n]$ 中有多少个这样的倍增数。

输入格式

输入一个正整数 $n$。

输出格式

输出一个整数，表示区间 $[1, n]$ 中倍增数的个数。

输入输出样例

12

出样例 $\tt \#1$说明

在 $[1, 12]$ 范围内：

• $12$ 是倍增数（$1 \times 2 = 2$）
• $24$ 大于 $12$，不计入
• 结果为 $1$

1

50

5

样例 $\tt \#2$说明

在 $[1, 50]$ 范围内：

• $12$：$1 \times 2 = 2$
• $24$：$2 \times 2 = 4$
• $36$：$3 \times 2 = 6$
• $48$：$4 \times 2 = 8$
• $50$：$5 \times 2 = 10 \rightarrow 0$
• 结果为 $5$

4321

42

数据范围

• 对于 $30\%$ 的数据， $1 \leq n \leq 10^{3}$
• 对于 $80\%$ 的数据，$1 \leq n \leq 10^{12}$
• 对于 $100\%$ 的数据，$1 \leq n \leq 10^{20}$