Сусідні цифри – різні

Обмеження: 2 сек., 256 МіБ

Марічку цікавить, скільки є натуральних чисел строго менших за $n$ таких, що не мають двох сусідніх однакових цифр у десятковому записі.

Допоможіть Зенику порахувати цю кількість для Марічки.

Вхідні дані

У єдиному рядку задано одне ціле число $n$.

Вихідні дані

У єдиному рядку виведіть одне ціле число — відповідь на задачу.

Обмеження

$1 \le n \le 10^{18}$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
47	42

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7474	5575

Примітки

У першому прикладі підходять усі числа від 1 до 46 включно, окрім 11, 22, 33 та 44.