题目描述

一个正整数，若能在它的十进制表示中找到一条分割线，将它分成两段，使得每段数字的力矩相等，则称这个数字为天平数。

力矩定义为每个数字到分割线的距离乘以数字大小的和。例如 对于 $222248$ 来说，如果将它分割为 $2222$ 与 $48$，则左侧力矩为

右侧力矩为

两者相等，所以 $222248$ 是一个天平数。

给定整数 $n$，请统计 $1$ 到 $n$ 之间有多少天平数。

输入格式

单个整数：表示 $n$。

输出格式

单个整数：表示天平数的数量。

100

9

样例解释 1

11,22,33,44,55,66,77,88,99以个位分割线

200

18

样例解释 2

11,22,33,44,55,66,77,88,99以个位分割线 102,113,124,135,146,157,168,179 以个位分割线 110 以十位分割线

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 1,000$
• 对于 $60\%$ 的数据，$1\leq n\leq 5,000,000$
• 对于 $100\%$ 的数据，$1\leq n\leq 10^{18}$