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

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

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

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

Вхідні дані

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

Вихідні дані

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

Обмеження

\(1 \le n \le 10^{18}\).

Приклади

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

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

Примітки

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