Почти палиндром

Описание задачи

Палиндром — это число, цифры которого читаются одинаково слева направо и справа налево. Примеры: $7$, $121$, $4004$.

Проверка на палиндромность выполняется следующим образом. Пусть число имеет длину $k$. Сравните первые $\lfloor k/2 \rfloor$ цифры с последними $\lfloor k/2 \rfloor$ цифрами по парам:

• 1-я цифра $\leftrightarrow$ последняя цифра,
• 2-я цифра $\leftrightarrow$ предпоследняя цифра,
• 3-я цифра $\leftrightarrow$ третья с конца цифра,
• и так далее.

Каждое такое сравнение называется парой. Если все пары равны, число является палиндромом.

Почти палиндром

Число называется почти палиндромом, если среди всех этих пар:

• только одна пара имеет разные цифры (только 1 несовпадающая пара),
• все остальные пары совпадают.

Таким образом, сами палиндромы (с $0$ несовпадающими парами) не являются почти палиндромами.

Заданное целое число $N$, подсчитайте, сколько почти палиндромных чисел находится в диапазоне от $1$ до $N$.

Формат ввода

Одно целое число $N$ ($1 \le N \le 10^{18}$).

Формат вывода

Выведите одно целое число — количество почти палиндромов в диапазоне $[1,\, N]$.

Оценка

15

5